2 6 0 9

Papyrus在审判你  •  1年前


#include<bits/stdc++.h>
using namespace std;
int n,m;
struct eggy{
    int s,t;
    int w;
}danzai[2000005];
bool jiujiu(eggy a,eggy b){
    return a.w<b.w;
}int ans=0,tot=0;
int f[100000];
int xianyu(int x){
    if(f[x]==x){
        return x;
    }
    else{
        f[x]=xianyu(f[x]);
        return f[x];
    }
}
void party(){
    for(int i=1;i<=m;i++){
        int u=xianyu(danzai[i].s);
        int v=xianyu(danzai[i].t);
        if(u==v){
            continue;
        }
        f[u]=v;
        ans+=danzai[i].w;
        tot+=1;
        if(tot==n-1){
            break;
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        f[i]=i;
    }
    for(int i=1;i<=m;i++){
        cin>>danzai[i].s>>danzai[i].t>>danzai[i].w;
    }
    sort(danzai+1,danzai+m+1,jiujiu);
    party();
    if(tot+1==n){
        cout<<ans;
    }
    else{
        cout<<"orz";
    }
    return 0;
}

评论:

请先登录,才能进行评论