求助,10pts
查看原帖
求助,10pts
793625
Pink_Cut_Tree楼主2023/12/23 14:51
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+4,M=1e5+5;
int n,m;
struct pri{
	int a,b,c;
	friend bool operator<(pri x,pri y){
		return x.c>y.c;
	}
}p[M];
int fa[N],e[N];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
	x=find(fa[x]);
	y=find(fa[y]);
	fa[x]=y;
}
bool check(int x,int y){
	return (find(x)==find(y));
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=m;i++){
		cin>>p[i].a>>p[i].b>>p[i].c;
	}
	sort(p+1,p+n+1);
	for(int i=1;i<=m+1;i++){
		if(check(p[i].a,p[i].b)){
			cout<<p[i].c; return 0;
		}
		if(!e[p[i].a]){
			e[p[i].a]=p[i].b;
		}
		else{
			merge(e[p[i].a],p[i].b);
		}
		if(!e[p[i].b]){
			e[p[i].b]=p[i].a;
		}
		else{
			merge(e[p[i].b],p[i].a);
		}
	}
return 0;
}

2023/12/23 14:51
加载中...