0%

[NOIp2010] 关押罪犯

题目

题目链接

题目大意:给出无向图 $G = (V, E)$,要求将该图删去一些边使得原图被分成两个没有交集的部分,使留下的边的最大值最小。$1 \le |V| \le 20000, 1 \le |E| \le 100000$。

思路

考虑贪心,每次都删去当前能删的边权最大的边。

先把所有边按边权排序。

现在相当于维护两个点的集合,如果当前要删的边的两个端点已经在同一集合里,也就是说这条边不能删掉,答案就是这条边的边权。

维护两个集合的操作可以用并查集完成。

最后别忘了答案有可能为 $0$。

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

struct Edge {
int u, v, w;
friend bool operator < (const Edge &a, const Edge &b) {
return a.w > b.w;
}
} g[100010];

int b[20010], f[20010];
int n, m;

int unionFind(int x) { return f[x] == x ? x : f[x] = unionFind(f[x]); }

int main() {
read(n), read(m);
for (int i = 1; i <= n; ++i) f[i] = i;
for (int i = 1; i <= m; ++i) read(g[i].u), read(g[i].v), read(g[i].w);
std::sort(g + 1, g + m + 1);
for (int i = 1; i <= m; ++i) {
if (unionFind(g[i].u) == unionFind(g[i].v)) {
printf("%d\n", g[i].w);
return 0;
}
if (!b[g[i].u]) b[g[i].u] = g[i].v;
else f[unionFind(b[g[i].u])] = unionFind(g[i].v);
if (!b[g[i].v]) b[g[i].v] = g[i].u;
else f[unionFind(b[g[i].v])] = unionFind(g[i].u);
}
puts("0");
return 0;
}