关押罪犯-题解

查看原题请戳这里

qxy做的第一道种类并查集的题目

种类并查集不会的戳这里 这道题基本上就是一个种类并查集的板子题，于是我们直接附一下代码好了：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define INF 0x7fffffff
#define ll long long

using namespace std;
int n,m,a,b,v,q,f[40005];
struct person{
    int x,y,w;
}p[100005];
int mysort(person x,person y)
{
    return x.w > y.w;
}
int find(int x)
{
    if(f[x] == x) return x;
    return f[x] = find(f[x]);
}
int main()
{
    scanf(“%d%d”,&n,&m);
    for(register int i = 1; i <= n; i++)
    {
        f[i] = i;
        f[i + n] = i + n;
    }
    for(register int i = 1; i <= m; i++) scanf(“%d%d%d”,&p[i].x,&p[i].y,&p[i].w);
    sort(p + 1, p + m + 1, mysort);
    for(register int i = 1; i <= m; i++)
    {
        a = p[i].x;
        b = p[i].y;
        v = p[i].w;
        if(find(a) == find(b) || find(a + n) == find(b + n))
        {
            cout << p[i].w;
            return 0;
        }
        f[find(a)] = f[find(b + n)];
        f[find(b)] = f[find(a + n)];
    }
    printf(“0”);
    return 0;
}