记录编号	342346	评测结果	AAAAAAAAAA
题目名称	[福州培训2010] 修复公路	最终得分	100
用户昵称	O(1)	是否通过	通过
代码语言	C++	运行时间	0.546 s
提交时间	2016-11-08 12:54:42	内存使用	0.32 MiB

#include<iostream>
#include<algorithm>
#include<fstream>
using namespace std;
int pre[1001];
struct aq
{
	int z,c,v;
};
bool haha(const aq &a,const aq &b)
{
	return a.v<b.v;
}
int afind(int x)
{
	int r=x;
	while(pre[r]!=r)
	   r=pre[r];
	   
	int i=x,j;
	while(i!=r)
	{
		j=pre[r];
		pre[i]=r;
		i=j;
	}
	return r;
}
void amix(int x,int y)
{
	int fx=afind(x),fy=afind(y);
	if(fx!=fy)
	   pre[fx]=fy;
	
}
int main()
{
	ofstream fout("roada.out");
	ifstream fin("roada.in");
	int n,m,i,j,k,s=0,sum=0;
	fin>>n>>m;
	aq a[m];
	for(i=1;i<=n;i++)
	   pre[i]=i;
	for(i=0;i<m;i++)
	{
		fin>>a[i].z>>a[i].c>>a[i].v;
	}
	sort(a,a+m,haha);
	for(i=0;i<m;i++)
	{
		if(afind(a[i].z)!=afind(a[i].c))
		{
			s=max(s,a[i].v);
			amix(a[i].z,a[i].c);
			sum++;
		}
		else
		continue;
	}
	if(sum==n-1)
	fout<<s<<endl;
	else
	fout<<"-1"<<endl;
	fin.close();
	fout.close();
	return 0;
}