题解 P1525 【关押罪犯】

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
struct bcj{                    //并查集
	int len;                   //长度
	int q[40005];              //存储，q[i]代表i的老大
	void init(int lenn){       //初始化一个长度为lenn的并查集
		len=lenn;
		for(int i=1;i<=len;i++)
			q[i]=i;
	}
	int Find(int t){           //找t的顶级老大
		if(q[t]==t) return t;
		else return Find(q[t]);
	}
	void in(int a,int w){      //将a及a的老大团加入w团
		if(q[a]!=a) in(q[a],w); 
		q[a]=w;
	} 
	void add(int a,int b){     //合并a和b所在老大团
		int a_1=Find(a),b_1=Find(b);
		q[a_1]=b_1;
		in(a,b_1);
	}
	int num(){                 //求老大团数
		int ans;
		for(int i=1;i<=len;i++)
			if(q[i]==i)
				ans++;
		return ans;
	}
	bool same(int a,int b){    //a和b是否在一个集合中
		int a_1=Find(a),b_1=Find(b);
		return a_1==b_1;
	}
}a;
struct Pair{
	int a,b,c;
}p[100005];
bool cmp(Pair q,Pair w){
	return q.c>w.c;
}
int n,m;
int main(){
	scanf("%d %d",&n,&m);
	a.init(n*2);
	for(int i=1;i<=m;i++)
		scanf("%d %d %d",&p[i].a,&p[i].b,&p[i].c);
	sort(p+1,p+m+1,cmp);
	for(int i=1;i<=m;i++){
		if(!a.same(p[i].a,p[i].b) && !a.same(p[i].a+n,p[i].b+n)){
			a.add(p[i].a,p[i].b+n);a.add(p[i].a+n,p[i].b);
		}else {
			printf("%d",p[i].c);
			return 0;
		}
	}
	printf("0");
	
	return 0;
}