题解 | #[NOIP2010]关押罪犯#

#include<algorithm>
using namespace std;
const int N = 20010;
const int M = 100010;
struct ct {
    int a;
    int b;
    int yq;
}cts[M];//记载冲突
int fa[N];//用于记录集合，同一并差集表示同一监狱
int ba[N];//记载威胁最大的敌人
bool cmp(ct a1, ct b1)
{
    return a1.yq > b1.yq;
}
int find(int a)
{
    if (a == fa[a]) return a;
    else return fa[a] = find(fa[a]);
}
void un(int a, int b)
{
    fa[find(a)] = find(b);
}
int n, m;
int main()
{
    cin >> n >> m;
    int cnt = 1;
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
    }
    for (int i = 1; i <= m; i++)
    {
        int a = 0, b = 0;
        cin >> a >> b >> cts[cnt].yq;
        cts[cnt].a = a;
        cts[cnt].b = b;
        cnt++;
    }//离线操作
    sort(cts + 1, cts + m + 1,cmp);
    //贪心思想，优先满足火气大的罪犯
    for (int i = 1; i <= m; i++)
    {
        int cr1 = cts[i].a;
        int cr2 = cts[i].b;
        int gfa = find(cr1);
        int gfb = find(cr2);
        if(!ba[cts[i].b])
        ba[cts[i].b] = cts[i].a;
        if (!ba[cts[i].a])
        ba[cts[i].a] = cts[i].b;//ba如果没有指向，那么代表节点在此之前没有冲突，此时把b作为a的敌人并查集的索引
        if (gfa != gfb)//不是一个集合说明可以分开
        {
            un(cr1, ba[cr2]);
            un(cr2, ba[cr1]);
        }
        else//是一个集合说明有一个矛盾更大的共同敌人，已经无法满足需要
        {
            cout << cts[i].yq;
            return 0;
        }
    }
    cout << 0;
    return 0;
}