将所有的罪犯关系按照怨气值大小排序。以敌人的敌人就就朋友的原则,对其进行合并。直到当前怨气最大的两个人之间
已经在一个监狱,那么这个值就是所需要的值。
对于如
2 1
1 2 2813
的特殊情况,在遍历时即可解决
#include<iostream>
#include<algorithm>
using namespace std;
const int N=20010,M=100010;
int b[N],f[N],num[N]={1};
int n,m;
struct criminal{
int x,y,w;
}c[M];
int findf(int x){
return f[x]==x?x:f[x]=findf(f[x]);
}
void merge(int x,int y){
x=findf(x);
y=findf(y);
if(num[x]<num[y])
swap(x,y);
f[y]=x;
num[x]+=num[y];
}
bool cmp(criminal a,criminal b){
return a.w>b.w;
}
bool check(int x,int y){
return findf(x)==findf(y);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=m;i++)
cin>>c[i].x>>c[i].y>>c[i].w;
sort(c+1,c+m+1,cmp);
for(int i=1;i<=m+1;i++){
if(check(c[i].x,c[i].y)){
printf("%d",c[i].w);
break;
}
else{
if(!b[c[i].x])
b[c[i].x]=c[i].y;
else
merge(b[c[i].x],c[i].y);
if(!b[c[i].y])
b[c[i].y]=c[i].x;
else
merge(b[c[i].y],c[i].x);
}
}
return 0;
}