记录编号	100059	评测结果	AAAAAAAAAA
题目名称	[福州培训2010] 修复公路	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.223 s
提交时间	2014-05-02 21:20:33	内存使用	1.46 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <set>
#include <list>
#include <queue>
#include <stack>
using namespace std;
struct ed
{
  int f,t,w;
}edge[100001];
int root[1001];
int findroot(int x);
bool cmp(ed a,ed b);
int main()
{
  freopen("roada.in","r",stdin);
  freopen("roada.out","w",stdout);
  int n,m;
  cin>>n>>m;
  for(int a=1;a<=n;a++)
    root[a]=a;
  for(int a=1;a<=m;a++)
    scanf("%d%d%d",&edge[a].f,&edge[a].t,&edge[a].w);
  sort(edge+1,edge+1+m,cmp);
  bool connect=false;
  int sum=0;
  int nown=1;
  for(int a=1;a<=m;a++)
  {
    int fr=findroot(edge[a].f);
    int tr=findroot(edge[a].t);
    if (fr!=tr)
    { 
      root[fr]=tr;
      nown++;
      sum=max(sum,edge[a].w);
    }
    if (nown==n)
    {
      connect=true;
      break;
    }
  }
  if (connect)
    printf("%d",sum);
  else 
    cout<<"-1";
  return 0;
}
//================
int findroot(int x)
{
  if (root[x]!=x)
    return root[x]=findroot(root[x]);
  else 
    return x;
}
bool cmp(ed a,ed b)
{
  return a.w<b.w;
}