P1525 [NOIP2010 提高组] 关押罪犯

带权并查集中，dist[]数组可以理解为一个向量，这样子比按照距离来理解更透彻：

优秀学习资料：

AcWing 240. 食物链(带权并查集) - AcWing

即d[a]表示向量a->fa[a]

这道题的并查集解法：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#define For(i, j, n) for (int i = j; i <= n; ++i)
using namespace std;

const int N = 20005, M = 100005;

int fa[N], d[N];
int n, m;
struct _edges
{
    int a, b, w;
    bool operator<(const _edges &t) const
    {
        return w > t.w;
    }
} Edge[M];

void init(int n)
{
    for (int i = 1; i <= n; i++)
        fa[i] = i;
}

int find(int a)
{
    if (a == fa[a])
        return a;
    int old_fa = fa[a];
    fa[a] = find(old_fa);
    d[a] = (d[a] + d[old_fa]) % 2;
    return fa[a];
}

int solve()
{
    for (int i = 1; i <= m + 1; i++)
    {
        int a = Edge[i].a, b = Edge[i].b;
        int x = find(a), y = find(b);
        if (x != y)
        {
            d[x] = (d[b] - d[a] + 3) % 2;
            fa[x] = y;
           // printf("D %d %d %d %d %d\n", a, b, x, y, d[x])
        }
        else
        {
            if((d[a] - d[b] + 2) % 2 == 0)
                return Edge[i].w;
        }
    }
    return 0;
}

int main()
{
    scanf("%d%d", &n, &m);
    init(n);
    int a, b, w;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &a, &b, &w);
        Edge[i] = {a, b, w};
    }
    Edge[m + 1] = {0, 0, 0};
    sort(Edge + 1, Edge + m + 1);
    cout << solve();
    return 0;
}

一开始把贪心想错了，把所有节点联通之后才开始计算答案，实际上，在整棵树连通之前，可能就已经有节点通过前面的边间接确定了关系，这时候它们就不得不分配在同一个监狱了，此时已经可以返回答案了。

解法二：

二分+二分图，二分一个权值的阈值，超过这个阈值的边，就把它们连起来，如果能够建立二分图（用二分图判定定理判断），就说明这个阈值还能够提高

这里边的实际含义相当于“不能住在同一个监狱”，如果能建立二分图的话，两个集合就分别表示两个监狱。边只存在于两个集合之间，而不存在于集合内部，现实含义就是：

监狱一和监狱二中的罪犯之间都不能住在一起，而集合内部没有边，即同一个监狱的罪犯都住在一起。