Kruscal37分求助
查看原帖
Kruscal37分求助
1219953
Forose楼主2023/12/24 10:58
#include<cstdio>
#include<algorithm>
#define long long
using namespace std;
const int N=2e5+10;
int n,m,a[N];
struct edge{
	int u,v,w;
}edges[N];
int cmp(edge a1,edge a2){
	return a1.w<a2.w;
}
int find(int x){
	if(a[x]!=x) x=find(a[x]);
	return a[x];
}
int kruscal(){
	int res=0,cnt=0;
	sort(edges+1,edges+m+1,cmp);
	for(int i=1;i<=n;i++){
		a[i]=i;
	}
	for(int i=1;i<=m;i++){
		if(find(edges[i].u)!=find(edges[i].v)){
			a[edges[i].u]=edges[i].v;
			res+=edges[i].w;
			cnt++;
			if(cnt==n-1) break;
		}                   
	}
	if(cnt==n-1) return res;
	else return -1;
}
signed main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&edges[i].u,&edges[i].v,&edges[i].w);
	}
	int ans=kruscal();
	if(ans==-1) printf("orz");
	else printf("%d",ans);
	return 0; 
}
2023/12/24 10:58
加载中...