要加判orz在哪里加怎么判啊

P3366 【模板】最小生成树

Eddy1341 @ 2024-08-19 21:14:21

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int cnt,fa[5005];
long long ans;
struct edge{
    int st,to;
    long long p;
}E[200005];
int findfa(int x){
    if(x==fa[x])return x;
    return fa[x]=findfa(fa[x]);
}
bool cmp(edge a,edge b){
    return a.p<b.p;
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&E[i].st,&E[i].to,&E[i].p);
    }
    sort(E+1,E+1+m,cmp);
    for(int i=1;i<=m;i++){
        int x=findfa(E[i].st),y=findfa(E[i].to);
        if(x==y)continue;
        ans+=E[i].p;
        fa[x]=y;
                if(++cnt==n-1)break;
    }
    printf("%lld",ans);
    return 0;
}

不想另外跑深搜qwq


by Eddy1341 @ 2024-08-19 21:15:33

最大的问题是,加了#13后,一堆不判orz的题解都过不了


by c20220526 @ 2024-08-19 21:17:57

循环完后cnt没到n-1就是不连通


by yyy_xiaohao @ 2024-08-19 21:18:51

刚想让你判一下每个节点的 root,然后发现你有 cnt。。。。。。

直接看 cnt 是不是 n - 1 不就好了吗


|