P1525 [NOIP2010 提高组] 关押罪犯

· · 题解

P1525 [NOIP2010 提高组] 关押罪犯

题目翻译：

题目的意识就是要把所有罪犯给分成两组，使其中有仇恨的囚犯尽可能少。或者使每个组的影响度最小；

思路：

我们可以发现，若两个人有仇恨的话，那尽量使这两个人不在一组即可。我们因此可以想到把所有罪犯仇恨所造成的影响从大到小进行排序。影响越大的就尽量分开，若实在分不开了，就输出。

实现：

那如何维护两个组？我们可以发现一个特点：敌人的敌人就是朋友，因此我们用并查集维护两个组，在用一数组来维护每个人的敌人，若没到一组仇恨关系时判断是否有敌人，再将他敌人的敌人与它合并到一起即可

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100000;
struct criminal{
    int u,v,w;
    bool operator<(const criminal &a){return w>a.w;}
}c[N];
int fa[N],b[N];
int find(int x){
    if(fa[x]==x)return x;
    else return fa[x]=find(fa[x]);
}
void merge(int x,int y){
    fa[find(x)]=find(y);
}
int main(){
    int n,m;
    cin>>n>>m;
    fa[0]=0;
    fa[-1]=-1;
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=1;i<=m;i++){
        cin>>c[i].u>>c[i].v>>c[i].w;
    }
    sort(c+1,c+1+m);
    for(int i=1;i<=m;i++){
        if(find(c[i].u)==find(c[i].v)){
            cout<<c[i].w;
            return 0;
        }
        if(!b[c[i].u])b[c[i].u]=c[i].v;
        else{
            merge(c[i].v,b[c[i].u]);
        }
        if(!b[c[i].v])b[c[i].v]=c[i].u;
        else{
            merge(c[i].u,b[c[i].v]);
        }
    }
    cout<<0;
}

并查集讲解