題目 關押罪犯
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX=20010;
const int MAXM=100010;
int father[MAX*2];
struct node{
int x,y,t;
friend bool operator < (const node &xx,const node &yy){
return xx.t > yy.t;
}
};
node a [MAXM];
int findset(int xx){
if(xx==father[xx])
return xx;
else
return father[xx]=findset(father[xx]);
}
void unionset(int xx,int yy){
xx=findset(xx);
yy=findset(yy);
if(xx!=yy)
father[xx]=yy;
}
int n,m,ans=0;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>a[i].x>>a[i].y>>a[i].t;
sort(a+1,a+m+1);
for(int i=1;i<=2*n;i++)
father[i]=i;
for(int i=1;i<=m;i++){
if(findset(a[i].x)!=findset(a[i].y)){
unionset(a[i].x,a[i].y+n);
unionset(a[i].y,a[i].x+n);
}
else{
ans=a[i].t;
break;
}
}
cout<<ans<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/276654.html
標籤：其他