记录编号	137202	评测结果	AAAAAAAAAAA
题目名称	[POJ2395] Out of Hay	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2014-11-04 14:53:05	内存使用	0.52 MiB

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;

int ret;
char ch;
int qin()
{
    ret=0;
    while(ch=getchar(),!isdigit(ch));
    while(ret=ret*10+ch-'0',ch=getchar(),isdigit(ch));
    return ret;
}

struct dx{
	int s,e,data;
};
dx a[20001];

int n,m;
int fa[2001];

int find(int x)
{
	if(fa[x]==x) return x;
	fa[x]=find(fa[x]);
	return fa[x];
}
bool comp(dx a,dx b){return a.data<b.data;}

int main()
{
    freopen("outofhay.in","r",stdin);
    freopen("outofhay.out","w",stdout);
	n=qin();m=qin();
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++) a[i].s=qin(),a[i].e=qin(),a[i].data=qin();
	sort(a+1,a+m+1,comp);
	int sum=0,maxx=0;
	for(int i=1;i<=m;i++)
	{
		int x=find(a[i].s),y=find(a[i].e);
		if(x!=y)
		{
			sum++;
			if(a[i].data>maxx) maxx=a[i].data;
			fa[y]=x;
		}
		if(sum==n-1) break;
	}
	if(sum<n-1) printf("-1\n");
	else printf("%d\n",maxx);
    return 0;
}