记录编号	534765	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	Richard	是否通过	通过
代码语言	C++	运行时间	0.435 s
提交时间	2019-07-03 11:16:43	内存使用	15.18 MiB

#include<bits/stdc++.h>
using namespace std;
int n,m,fa[100001];
struct criminal{
	int j,y,fight;
}s[100001];
bool cmp(criminal a,criminal b){
	return a.fight>b.fight;
}
int get(int x){//关入同一监狱即为合并 
	if(fa[x]==x)
		return x;
	return fa[x]=get(fa[x]);
}
int main()
    {
    freopen("prison1.in","r",stdin);
    freopen("prison1.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n*2;i++)
		fa[i]=i;//初始化 
	for(int i=1;i<=m;i++){
		cin>>s[i].j>>s[i].y>>s[i].fight;	
	}
	sort(s+1,s+m+1,cmp);//从高到低排序权值 
	for(int i=1;i<=m;i++){
		int xx=get(s[i].j);
		int yy=get(s[i].y);
		if(xx==yy)
		{
		cout<<s[i].fight;//在同一监狱且有冲突输出冲突值 
		return 0;	
		}
		fa[xx]=get(s[i].y+n);//借鉴大佬们的处理 
		fa[yy]=get(s[i].j+n);
	}
	cout<<0;//无冲突时输出零 
	return 0;
    }