最小生成树

potatoplanet720 · 2024-11-23 10:21:25 · 算法·理论

#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;
}