P3366 【模板】最小生成树

点击查看代码

#include<bits/stdc++.h>
using namespace std;

const int N=5050,M=2e5+10;
int n,m;

struct Edge{
    int a,b,w;
    bool operator<(const Edge& W) const{
        return w<W.w;
    }
}edges[M];

int p[N];
long long res,cnt;
int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

bool kruskal()
{
    sort(edges+1,edges+1+m);

    for(int i=1;i<=n;i++){
        p[i]=i;
    }

    for(int i=1;i<=m;i++){
        int a,b,w;
        a=find(edges[i].a),b=find(edges[i].b),w=edges[i].w;
        if(a!=b){
            p[a]=b;
            res+=w;
            if(++cnt==n-1) break;
        }
    }

    if(cnt<n-1) return false;
    else return true;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>edges[i].a>>edges[i].b>>edges[i].w;
    }

    
    if(kruskal()){
        cout<<res<<"\n";
    }else{
        cout<<"orz"<<"\n";
    }

    return 0;
}