求调 p1525 关押罪犯

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e4+5;
const int maxm=1e5+5;
int n,m;
int fa[maxn],e[maxn];
struct node{
	int x,y,z;
}a[maxm];
bool cmp(node a,node b){
	return a.z>b.z;
}
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
	}
	sort(a+1,a+m+1,cmp);
	bool ok=1;
	for(int i=1;i<=m;i++){
		int x=find(a[i].x),y=find(a[i].y);
		if(x==y){
			printf("%d",a[i].z);
			ok=0;
			break;
		}else{
			if(!e[a[i].x]) e[a[i].x]=a[i].y;
			else fa[e[a[i].x]]=a[i].y;
			if(!e[a[i].y]) e[a[i].y]=a[i].x;
			else fa[e[a[i].y]]=a[i].x;
		}
	}
	if(ok) cout<<0;
	return 0;
}