[BZOJ 2753][SCOI 2012] 滑雪与时间胶囊

题目大意

给定一个 \(n\) 个节点、\(m\) 条无向带权边的图,每个节点有一个高度 \(h_i\),只能从某一个节点走到高度不大于其的点;另外,可以无数次的回到上一个节点。求最多能访问多少节点,以及此时的最短距离。

\(1 \leqslant n \leqslant 100,000\)

\(1 \leqslant m \leqslant 1,000,000\)

\(1 \leqslant w_i, \; h_i \leqslant 1,000,000,000\)

题目链接

BZOJ 2753

CodeVS 2399

题解

由于有高度的限制,无向边其实是有向边(相同高度就是两条),第一问随便遍历一遍图就行了,而第二问就是要求最小树形图。求最小树形图的朱刘算法,虽然我不会,但它的复杂度为 \(O(nm)\),会 TLE。考虑 Kruskal 为什么不能求解:因为边的有向可能会导致中间某条边是反向的,使得由根无法到达更下的节点。但对于同一高度的点,Kruskal 是正确的,故把边以高度为第一关键字、边权为第二关键字排序,做 Kruskal。

算个神题吧。。。(或者我好菜啊。。。)

才发现之前的题解中「Kruskal」好像拼错了,代码也是刚改的(提上去的拼写也是错的)。。。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <queue>
#include <algorithm>
// #define DBG
const int MAXN = 100005;
const int MAXM = 1000005;
struct Edge;
struct Node {
Edge *e;
int height;
bool vis;
#ifdef DBG
int id;
#endif
} N[MAXN];
struct Edge {
Node *u, *v;
Edge *next;
Edge(Node *u, Node *v) : u(u), v(v), next(u->e) {}
};
void addEdge(int u, int v) {
#ifdef DBG
printf("edge : %d --> %d\n", u, v);
#endif
N[u].e = new Edge(&N[u], &N[v]);
}
struct Pair {
int u, v, w;
bool operator<(const Pair &another) const {
return N[v].height == N[another.v].height ? w < another.w : N[v].height > N[another.v].height;
}
} E[MAXM];
int n, m;
int bfs() {
int res = 1;
std::queue<Node *> q;
q.push(&N[1]);
N[1].vis = true;
while (!q.empty()) {
Node *u = q.front();
q.pop();
#ifdef DBG
printf("bfs(%d)\n", u->id);
#endif
for (Edge *e = u->e; e; e = e->next) {
#ifdef DBG
printf("bfs(%d), v = %d\n", u->id, e->v->id);
#endif
if (!e->v->vis) {
e->v->vis = true;
res++;
q.push(e->v);
}
}
}
return res;
}
namespace Kruskal {
struct UnionFindSet {
int fa[MAXN];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void init(int n) {
for (int i = 1; i <= n; i++) fa[i] = i;
}
} ufs;
long long solve() {
ufs.init(n);
std::sort(E, E + m);
long long res = 0;
for (int i = 0; i < m; i++) {
if (!N[E[i].u].vis || !N[E[i].v].vis) continue;
int p = ufs.find(E[i].u), q = ufs.find(E[i].v);
if (p == q) continue;
ufs.fa[q] = p;
res += E[i].w;
}
return res;
}
}
int main() {
scanf("%d %d", &n, &m);
#ifdef DBG
for (int i = 1; i <= n; i++) N[i].id = i;
#endif
for (int i = 1; i <= n; i++) scanf("%d", &N[i].height);
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &E[i].u, &E[i].v, &E[i].w);
if (N[E[i].u].height < N[E[i].v].height) std::swap(E[i].u, E[i].v);
addEdge(E[i].u, E[i].v);
if (N[E[i].u].height == N[E[i].v].height) addEdge(E[i].v, E[i].u);
}
printf("%d ", bfs());
printf("%lld\n", Kruskal::solve());
return 0;
}