哪位大佬帮忙看一下kluskal,谢谢
  • 板块P2820 局域网
  • 楼主Iamhero
  • 当前回复8
  • 已保存回复8
  • 发布时间2022/8/11 22:41
  • 上次更新2023/10/27 15:51:45
查看原帖
哪位大佬帮忙看一下kluskal,谢谢
468944
Iamhero楼主2022/8/11 22:41
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct dy{
	int x;
	int y;
	int z;
};
dy a[5010];
int father[1010],n,m,ans;
int cmp(const dy &a,const dy &b){
	if(a.z<=b.z)
		return 1;
	return 0;
}
int find(int x){
	if(father[x]!=x)
		father[x]=find(father[x]);
	return father[x];
}
int main(){
	ios::sync_with_stdio(false);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		cin>>a[i].x>>a[i].y>>a[i].z;
		ans+=a[i].z;
	}
	for(int i=1;i<=n;i++)
		father[i]=i;
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++){
		int fx=find(a[i].x);
		int fy=find(a[i].y);
		if(fx!=fy){
			father[fy]=fx;
			ans-=a[i].z;
		}
	}
	printf("%d",ans);
	return 0;
}
2022/8/11 22:41
加载中...