大佬求助kruskal WA了好几个点。。。

P3366 【模板】最小生成树

胖达和阿极 @ 2022-07-26 23:00:19

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
int n,m,fa[N];
struct edge{
    int u,v,w;
    bool operator <(const edge &a1) const{
        return w<a1.w;
    }
}a[N];
int find(int x){
    return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
}
bool cmp(edge a1,edge a2){
    return a1.w<a2.w;
}
long long kruskal()
{
    long long  cnt = 0,sum =0;
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++){
        if(find(a[i].u)!=find(a[i].v)){
            fa[a[i].v] = fa[a[i].u];
            sum += a[i].w;
            cnt++;
            if(cnt == n-1){
                return sum;
            }
        }
    }
    return -1;
}
int main(){
    cin>>n>>m;
    int g1,g2,g3;
    for(int i=1;i<=n;i++){
        fa[i] = i;
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&g1,&g2,&g3);
        a[i].u=g1;a[i].w=g3;a[i].v=g2;

    }
    int k1 = kruskal();
    if(k1==-1){
        cout<<"orz";
    }else{
        cout<<k1;
    }
    return 0;
}

by Benny_Li @ 2022-10-05 20:33:45

另外这种涉及图论的题目竟然只有\colorbox{orange}{\color{white}{普及-}}有点离谱了,这么说一堆\colorbox{purple}{\color{white}{省选/NOI-}}和$ \colorbox{black}{\color{white}{NOI/NOI+/CTSC}}

岂不是都……

上一页 |