记录编号	593691	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	0.439 s
提交时间	2024-09-09 00:33:39	内存使用	3.76 MiB

#include<bits/stdc++.h>
using namespace std;
int n,k,fa[40010],m,ans;
inline int read()
{
    int sum=0;
    char ch=getchar();
    while(ch>'9'||ch<'0') ch=getchar();
    while(ch>='0'&&ch<='9') sum=sum*10+ch-48,ch=getchar();
    return sum;
}
struct node{
	int x;
	int y;
	int z;
}e[100010];
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]);
}
void join(int x,int y){
	int rx=find(x),ry=find(y);
	fa[ry]=rx;
}
int main(){
	 freopen("prison1.in","r",stdin);
    freopen("prison1.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=2*n;i++)
	fa[i]=i;
	for(int i=1;i<=m;i++)
	cin>>e[i].x>>e[i].y>>e[i].z;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++){
		int x=e[i].x,y=e[i].y,z=e[i].z;
		if(find(x+n)!=find(y+n)){
			join(x+n,y);
			join(x,y+n);
		}
		else{
			join(x,y);
			join(x+n,y+n);
			ans=max(ans,z);
		}
	}
	cout<<ans;
	return 0;
}