比赛 暑期小训练题 评测结果 AAAAAAAAAA
题目名称 修复公路 最终得分 100
用户昵称 nichengyan 运行时间 0.565 s
代码语言 C++ 内存使用 40.07 MiB
提交时间 2021-07-11 21:17:37
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int maxn=1500;
int f[maxn*maxn];
int find(int k){
	return k==f[k]?k:f[k]=find(f[k]);
}
struct s{
	int u,v,w;
}edge[maxn*maxn];
int cnt=1;
int v,e;
void init(){
	cin>>v>>e;
	for(int i=1;i<=e;i++){
		int a,b,c;
		cin>>a>>b>>c;
		edge[cnt].u=a;
		edge[cnt].v=b;
		edge[cnt].w=c;
		cnt++;
	}
}
bool cmp(s a,s b){
	return a.w<b.w;
}
int main(){
	freopen("roada.in","r",stdin);
	freopen("roada.out","w",stdout);
	init();
	sort(edge+1,edge+1+cnt,cmp);
	for(int i=1;i<=maxn*maxn;i++){
		f[i]=i;
	}
	int c=v;
	int ans=-1;
	for(int i=1;i<=cnt;i++){
		if(find(edge[i].u)!=find(edge[i].v)){
			f[find(edge[i].u)]=find(edge[i].v);
			ans=max(ans,edge[i].w);
			c--;
		}
	}
	if(c==1){
		cout<<ans;
	}else{
		cout<<-1;
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}