WA on #13

P3366 【模板】最小生成树

hsy20101122 @ 2024-02-19 22:35:09


#include<bits/stdc++.h> 
using namespace std;
int n,m,fa[200001],ans;
struct edge{
    int u,v,w;
}e[200001];
bool cmp(edge a,edge b){
    return a.w<b.w;
}
int getfather(int x){
    if(x==fa[x]){
        return x;
    }
    return fa[x]=getfather(fa[x]);
}
int main(){ 
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=1;i<=m;i++){
        cin>>e[i].u>>e[i].v>>e[i].w; 
    }
    sort(e+1,e+1+m,cmp);
    for(int i=1;i<=m;i++){
        int eu=getfather(e[i].u);
        int ev=getfather(e[i].v);
        if(eu==ev){
            continue;
        }
        fa[eu]=ev;
        ans+=e[i].w;
    }
    if(ans>0){
        cout<<ans; 
    }else{
        cout<<"orz";
    }
    return 0;
}```

by gotocspandbetter @ 2024-02-19 22:47:44

将判断输出orz的条件改为最小生成树的边数是否等于节点数减1,是输出ans,不是输出orz


by gotocspandbetter @ 2024-02-19 22:48:07

@huangshuyuan2010


by gotocspandbetter @ 2024-02-19 22:51:29

一张图要连通,则至少需要n-1条边


by hsy20101122 @ 2024-02-20 13:39:20

@gotocspandbetter 谢谢大神


|