记录编号	157546	评测结果	AAAAAAAAAAA
题目名称	[POJ2395] Out of Hay	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.057 s
提交时间	2015-04-09 11:33:49	内存使用	14.12 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Edge{
	int qs,zz,w;
}E[1200000];
long long f[10000],ans=0,k=0,n,m;
 
int find(int x) 
{ 
     return x==f[x]?x:f[x]=find(f[x]);  
}
  
void uinon(int x,int y)  
{  
    int p=find(x),q=find(y);  
    if(p!=q)  
    {  
        f[p]=q;   
    }  
} 
 
int cmp(const Edge &x,const Edge &y){
	return x.w<y.w;
} 
 
int main()
{
 freopen("outofhay.in","r",stdin);
 freopen("outofhay.out","w",stdout);
 cin>>n>>m;
 for (int i=1;i<=n;++i)
  f[i]=i;
 for (int i=1;i<=m;++i)
  {
  	int x,y,z;
  	cin>>x>>y>>z;
  	{
  		E[i].qs=x;
  		E[i].zz=y;
  		E[i].w=z;
  	}
  } 
 sort(E+1,E+m+1,cmp);
 for (int i=1;i<=m;++i)
 {
 	if (find(E[i].qs)!=find(E[i].zz))
 	{
 		uinon(E[i].qs,E[i].zz);
 		if (E[i].w>ans) ans=E[i].w;
 		k++;
 	}
 	if (k==n-1) 
 	{
 		cout<<ans;
 		return 0;
 	}
 }
 cout<<"-1";
 return 0;
}