P1525 [NOIP2010 提高组] 关押罪犯

原题链接

题解

这题我采用了带权并查集的做法，0代表两囚犯处于监狱，1代表两囚犯不同监狱。

根据题意，我们想让冲突值尽可能的小，那么我们要先把仇恨值大的两罪犯放在不同监狱；即按仇恨值从大到小的去判断每条仇恨信息。（贪心思想）

code

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+5;
const int M=1e5+5;
int father[N],dis[N];
int n,m;
struct Node{
    int one,two,value;
};
Node a[M];
void build(){
    for (int i=1;i<=n;i++) father[i]=i;
}
int find(int x){
    if (x==father[x]) return x;
    int r=find(father[x]);
    dis[x]=(dis[x]+dis[father[x]])%2;
    father[x]=r;
    return r;
}
bool cmp(Node a,Node b){
    return a.value>b.value;
}
int main(){
    cin>>n>>m;
    build();
    for (int i=1;i<=m;i++) cin>>a[i].one>>a[i].two>>a[i].value;
    sort(a+1,a+m+1,cmp);
    bool bol=true;
    for (int i=1;i<=m;i++){
        int fx=find(a[i].one),fy=find(a[i].two);
        if (fx==fy && dis[a[i].one]==dis[a[i].two]){
            cout<<a[i].value<<endl;
            bol=false;
            break;
        }
        else if (fx!=fy){
            dis[fx]=(dis[a[i].two]+1-dis[a[i].one]+2)%2;
            father[fx]=fy;
        }
    }
    if (bol) cout<<0<<endl;
    return 0;
}