专栏文章

最小生成树

算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir1admz
此快照首次捕获于
2025/12/04 14:07
3 个月前
此快照最后确认于
2025/12/04 14:07
3 个月前
查看原文
CPP
#include<bits/stdc++.h>
using namespace std;
struct rnfmabj{
	int x,y,z;
}a[2000005];
int fa[2000005];
bool cmp(rnfmabj o,rnfmabj p){
	return o.z<p.z;
}
int find(int x){
	if(fa[x]==x) return x;
	fa[x]=find(fa[x]);
	return fa[x];
}
int main(){
	int n,m,ans=0,op=0;
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>a[i].x>>a[i].y>>a[i].z;
	for(int i=1;i<=m;i++) fa[i]=i;
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++){
		int xx=a[i].x,yy=a[i].y;
		find(xx),find(yy);
		if(fa[xx]!=fa[yy]){
			ans+=a[i].z;
			op++;
			fa[fa[xx]]=fa[yy];
		}
		if(op==n-1) break;
	}
	if(op<n-1) cout<<"orz";
	else cout<<ans;
	return 0;
}

评论

0 条评论,欢迎与作者交流。

正在加载评论...