20pts,求助
查看原帖
20pts,求助
907430
corner_xiejunqi楼主2024/8/12 16:13
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+20;
struct node{
	int x,y,t;
}e[N];
int n,m;
bool cmp(node a,node b){
	return a.t<b.t;
} 
int fa[N];
int find(int a){
	if(fa[a]==a){
		return a;
	}else{
		return fa[a]=find(fa[a]);
	}
}
bool merge(int a,int b){
	int t1=find(a);
	int t2=find(b);
	if(t1!=t2){
		fa[t1]=t2;
		return 1;
	}
	return 0;
}
int main(){
	//1、声明变量,输入
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>e[i].x>>e[i].y>>e[i].t;
	}
	sort(e+1,e+1+n,cmp);
	//2、计算过程
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	int cnt=0;
	int maxn=0;
	bool f=true;
	for(int i=1;i<=m;i++){
		if(merge(e[i].x,e[i].y)){
			cnt++;
			maxn=max(maxn,e[i].t);
		}
		if(cnt==n-1){
			f=false;
			break;
		}
	}
	//3、输出
	if(f){
		cout<<-1;
	}else{
		cout<<maxn;
	}
	return 0;
}
2024/8/12 16:13
加载中...