Kruskal算法84pts求助
查看原帖
Kruskal算法84pts求助
500803
zzxzzxCCC楼主2023/8/15 20:35
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
struct rec{
	int x,y,z;
}edge[500010];
bool operator <(rec a,rec b){
	return a.z<b.z;
}
int fa[100010],n,m;
int getfa(int x){
    if(x==fa[x]) return x;
    return fa[x]=getfa(fa[x]);
}
int main(){
	int ans=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	    scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);
	for(int i=1;i<=n;i++) fa[i]=i;
	sort(edge+1,edge+m+1);
	for(int i=1;i<=m;i++){
		int x=getfa(edge[i].x),y=getfa(edge[i].y);
		if(x==y) continue;
		fa[x]=y;
		ans+=edge[i].z;
	}
	if(ans==0) { printf("orz");return 0;}
	printf("%d",ans);
	return 0;
}
2023/8/15 20:35
加载中...