记录编号 135034 评测结果 AAAAAAAAAA
题目名称 [福州培训2010] 修复公路 最终得分 100
用户昵称 Gravatar乌龙猹 是否通过 通过
代码语言 C++ 运行时间 0.202 s
提交时间 2014-10-31 15:15:28 内存使用 1.01 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[100001];

int n,m;
int fa[1001];

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("roada.in","r",stdin);
    freopen("roada.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;
}