记录编号	227088	评测结果	AAAAAAAAAA
题目名称	[福州培训2010] 修复公路	最终得分	100
用户昵称	水墨青花	是否通过	通过
代码语言	C++	运行时间	0.564 s
提交时间	2016-02-18 14:56:15	内存使用	0.44 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;

struct EDGE 
{
	int s;//start
	int e;//end
	int w;
}e[100001];

void Kruskal();
int Findroot(int);
void Union(int,int);
int comp(const struct EDGE& a,const struct EDGE& b)
{
	return a.w<b.w;
}

int n,m;
int father[1001];
int total=0;

int main()
{
	freopen("roada.in","r",stdin);
	freopen("roada.out","w",stdout);		
	
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		father[i]=i;
	}
	
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&e[i].s,&e[i].e,&e[i].w);
	}
	sort(e+1,e+1+m,comp);
	for(int i=1;i<=m;i++)
	{
	//	cout<<e[i].w<<"aaa"<<endl;
	}
	
	Kruskal();
	
	for(int i=1;i<=n-1;i++)
	{
		if(Findroot(i)!=Findroot(i+1))
		{
			printf("%d",-1);
			return 0;
		}
	}
	
	printf("%d",total);
	
	fclose(stdin);
	fclose(stdout);
	return 0;	
}

void Kruskal()
{
	for(int i=1;i<=m;i++)
	{
		if(Findroot(e[i].s)!=Findroot(e[i].e))
		{
			total=e[i].w;
	//		cout<<e[i].s<<' '<<e[i].e<<' '<<e[i].w<<endl;
	//		cout<<father[e[i].s]<<' '<<father[e[i].e]<<endl<<endl;
			Union(Findroot(e[i].s),Findroot(e[i].e));
		}
		else
		{
			continue;
		}
		
	}
}

void Union(int x,int y)
{
	father[x]=y;
}

int Findroot(int x)
{
	if(father[x]!=x)
	{
		father[x]=Findroot(father[x]);
	}
	return father[x];
}