就对一个,求助大佬!!!
  • 板块P1111 修复公路
  • 楼主wdzxghl
  • 当前回复11
  • 已保存回复11
  • 发布时间2020/6/18 13:10
  • 上次更新2023/11/7 00:27:07
查看原帖
就对一个,求助大佬!!!
266774
wdzxghl楼主2020/6/18 13:10
#include<bits/stdc++.h>
using namespace std;
const int inf=200010;
int n,m;
struct eg {
	int x,y,w;
} f[inf];
int fa[inf];
bool cmp(eg x,eg y) {
	return x.w<y.w;
}
int find(int x) {
	if(fa[x]!=x)  fa[x]=find(fa[x]);
	return x;
}

int main() {
	cin>>n>>m;
	for(int i=1; i<=m; i++)
		cin>>f[i].x>>f[i].y>>f[i].w;
	int ans=0;
	for(int i=1; i<=n; i++)fa[i]=i;
	sort(f+1,f+m+1,cmp);
	int tot=0;
	for(int j=1; j<=m; j++){
		int x=find(f[j].x);
		int y=find(f[j].y);
		fa[x]=y;
		if(x==y)continue;
		ans=max(ans,f[j].w);
		if(++tot==n-1){
			cout<<ans<<endl;
			return 0;
		}
	}
	cout<<-1<<endl;
	return 0;
}
2020/6/18 13:10
加载中...