专栏文章
最小生成树
算法·理论参与者 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 条评论,欢迎与作者交流。
正在加载评论...