44分求助T_T

P3366 【模板】最小生成树

Lance1_1 @ 2023-10-26 13:37:49

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

by Missdie @ 2023-10-26 14:20:29

for (int i = 1; i <= m; i ++){
        int qx = que(e[i].u);
        int qy = que(e[i].v);
        if (qx == qy) continue;
        fa[qx] = qy;
        cnt ++, sum += e[i].w;
    }
    if (cnt < n) puts("orz");
    else printf("%lld", sum);

这样子会舒服一点


by cy1999_de_dog @ 2023-10-26 14:35:52

check函数写错了

找两个点的祖先是否相同,而非他们父亲


by Lance1_1 @ 2023-10-26 16:04:25

@cy1999_de_dog 谢谢您!通过了!


by Lance1_1 @ 2023-10-26 16:05:05

@Missdie 好的,谢谢您!


|