[NOIp2010] 关押罪犯

题目

题目链接

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

思路

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

先把所有边按边权排序。

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

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

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

代码

#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;
}