记录编号	535090	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	欧鹰123	是否通过	通过
代码语言	C++	运行时间	0.352 s
提交时间	2019-07-04 07:40:59	内存使用	15.96 MiB

#include<bits/stdc++.h>

using namespace std;

int n,m,fa[100500],vis[100500],father[100500],ans;

struct node{
	int x,y,w;
}a[100500];

int find(int k)
{
	if(fa[k]==k)return k;
	else return fa[k]=find(fa[k]); 
}

bool cmp(node a,node b)
{
	return a.w>b.w;
}

int main()

{
	freopen("prison1.in","r",stdin);
	freopen("prison1.out","w",stdout);
	
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)fa[i]=i;
	
	for(int i=1;i<=m;i++)
	
	{
		cin>>a[i].x>>a[i].y>>a[i].w;
	}
	
	sort(a+1,a+1+m,cmp);
	
	for(int i=1;i<=m;i++)
	{
		int x=a[i].x,y=a[i].y,w=a[i].w;
		if(find(x)==find(y))
		{
			cout<<a[i].w;
			return 0;
		}
	    if(father[x]==0)
	      {
	      	father[x]=y;
		  }
	   else
	   {
	   	fa[find(father[x])]=find(y);
	   	//if(vis[father[x]]==0)vis[father[x]]=1,ans++;
	   	//if(vis[y]==0)vis[y]=1,ans++;
	   }
	   if(father[y]==0)
	      {
	      	father[y]=x;
		  }
	   else
	   {
	   	fa[find(father[y])]=find(x);
	   	//if(vis[father[y]]==0)vis[father[y]]=1,ans++;
	   	//if(vis[x]==0)vis[x]=1,ans++;
	   }
	}
	
	cout<<0;
	
	
	return 0;
	
}