记录编号	534813	评测结果	AAAAAAAAAA
题目名称	[福州培训2010] 修复公路	最终得分	100
用户昵称	Richard	是否通过	通过
代码语言	C++	运行时间	0.576 s
提交时间	2019-07-03 11:54:25	内存使用	15.18 MiB

#include<bits/stdc++.h>
using namespace std;
int n,m,fa[100001]; 
struct road{
	int j,y,time;
}s[100001];
bool cmp(road a,road b){
	return a.time<b.time;//升序排列权值 
}
int find(int x)//并查集查找 
{
 	if(fa[x]==x) 
 	return x;
	return fa[x]=find(fa[x]);
}
int main()
    {
    freopen("roada.in","r",stdin);
    freopen("roada.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		fa[i]=i;//初始化 
	for(int i=1;i<=m;i++){
		cin>>s[i].j>>s[i].y>>s[i].time;
	}
	sort(s+1,s+m+1,cmp);
	int bian=0,ans=0;
	for(int i=1;i<=m;i++){
		int xx=find(s[i].j);
		int yy=find(s[i].y);
		if(xx!=yy){//并查集合并 
			ans=s[i].time;//本题不是累加 各个公路同时修建 只需找出连通时最长的用时即可 /*ans+=s[i].time 
			fa[xx]=yy;
			bian++;
			if(bian==n-1)//当边数符合时结束 
				break;
		}
	}
	if(bian<n-1)
		cout<<-1;//不连通输出-1 
	else
		cout<<ans;
	return 0;
    }
    //核心思想Kruskal算法利用权值的大小以及对边个数的存储达到跳出循环及找出最短用时的目的
	//利用并查集对已修建公路的村庄进行合并以及查询