44分求助T_T
查看原帖
44分求助T_T
906023
Lance1_1楼主2023/10/26 13:37
#include<iostream>
#include<algorithm>

using namespace std;

const int maxn=200005;
int cnt,res=0,num=0;
int fa[5005];
struct edge{
    int to,next,val;
}e[maxn];
int n,m;

bool cmp(edge a,edge b){
    return a.val<b.val;
}
void iint(int n){
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
}
int find(int k){
   if(fa[k]==k)return k;
    else return fa[k]=find(fa[k]);
}

void Union(int x,int y){
    x=find(x);
    y=find(y);
    if(x!=y)    fa[y]=x;
}

bool check(int x,int y){
    if(fa[x]==fa[y]) return true;
    else return false;
}

int main(){
    cin>>n>>m;
    iint(n);
    for(int i=1;i<=m;i++){
        cin>>e[i].to>>e[i].next>>e[i].val;
    }
    sort(e+1,e+m+1,cmp);
    cnt=0;
    for(int i=1;i<=m;i++){
        if(cnt==n-1)    break;
        if(check(e[i].to,e[i].next)==false){
            Union(e[i].to,e[i].next);
            res+=e[i].val;
            cnt++;
        }
    }
    if(cnt==n-1){
        cout<<res<<endl;
    }
    else{
        cout<<"orz"<<endl;
    }
    return 0;
}
2023/10/26 13:37
加载中...