本文主要是介绍(Luogu) P1525 关押罪犯 (并查集)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
题目大意：1~n个人，一张关系网，连线权值代表起冲突的影响力，将n个人分成两部分，求最小的冲突事件影响力。如图
答案为3512.
解题思路：我们当然不希望权值大的边存在，所以将边从大到小排序，逐个处理，边所对的两方各为敌方，我们应该将一个人和他敌人的敌人并到一个集合，每一次合并都相当于去掉了这条边，从大到小去，当发现了这条边的两段已经在一个集合了，说明在前面合并去掉大边的时候，合并了两段，所以不可避免地这条边的权值就是答案。当合并了m条边时还没有输出，那就说明没有冲突。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int maxn=2e4+5;
int fa[maxn],rk[maxn],b[maxn];//b数组用来记录最大的仇人
int n,m;
struct edge{int s,e,w;
}eg[100005];
bool cmp(edge a,edge b){return a.w>b.w;
}
void init(){for(int i=0;i<maxn;++i){fa[i]=i;rk[i]=1;}
}
inline int find(int x){if(x==fa[x]) return fa[x];else return fa[x]=find(fa[x]);
}
inline bool ck(int x,int y){x=find(x),y=find(y);if(x==y) return true;else return false;
}
inline void unite(int x,int y){x=find(x),y=find(y);if(rk[x]<rk[y]){fa[x]=y;}else{if(rk[x]==rk[y]) rk[x]++;fa[y]=x;}
}
int main(){std::ios::sync_with_stdio(0);init();cin>>n>>m;for(int i=1;i<=m;++i){cin>>eg[i].s>>eg[i].e>>eg[i].w;}sort(eg+1,eg+1+m,cmp);int i,s,e;for(i=1;i<=m;++i){s=eg[i].s,e=eg[i].e;if(ck(s,e)){cout<<eg[i].w<<endl;break;}else{if(!b[s]) b[s]=e; //记录最大的仇人else unite(b[s],e); //与敌人的敌人合并if(!b[e]) b[e]=s;else unite(b[e],s);}}if(i==m+1) cout<<0<<endl;return 0;
}
这篇关于(Luogu) P1525 关押罪犯 (并查集)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
