AcWing 257. 关押罪犯 （并查集）打卡

题目：https://www.acwing.com/problem/content/description/259/

题意:有两个监狱，监狱里面有很多犯人，现在有很多对冲突，还有个冲突值，现在问我们怎么重新分配，能使这个最大冲突值尽量小，求这个冲突值

思路：首先我们只关心最大冲突值是多少，所以我们应该避免让大事件发生，所以我们排个序，从大到小，然后一条条建边，然后因为每条边我们要考虑分别放入哪个监狱，这又牵扯到一个顺序的问题，这里我们就直接建立一个中间点，两种情况都考虑即可

#include<bits/stdc++.h>
#define maxn 100005
#define mod 1000000007
using namespace std;
typedef long long ll;
struct sss
{
    ll x,y,z;
}a[maxn];
ll f[maxn];
ll n,m;
ll x,y,z;
ll find(ll x){
    if(x==f[x]) return x;
    else return f[x]=find(f[x]);
}
int cmp(struct sss x,struct sss y){
    return x.z>y.z;
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n<<1;i++){
        f[i]=i;    
    } 
    for(int i=0;i<m;i++){
        scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z);
    }
    sort(a,a+m,cmp);
    for(int i=0;i<m;i++){
        ll xx=find(a[i].x);
        ll yy=find(a[i].y);
        if(xx==yy){
            printf("%lld",a[i].z);
            return 0;
        }
        f[xx]=find(a[i].y+n);
        f[yy]=find(a[i].x+n);
    }
    printf("0");
}