84分求助

P3366 【模板】最小生成树

zp20120123 @ 2024-07-27 13:30:38

orz无敌了

附上错误代码

//kruskal
//最小生成树
//small
//sort

#include<bits/stdc++.h>
using namespace std;

int fa[5005];

struct node{
    int u, v, w;
}a[200005];

bool cmp(node x, node y){
    return x.w < y.w;
}

int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y){
    fa[find(x)] = find(y);
}

inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
signed main(){
    int n = read(), m = read();
    for(int i = 0; i < m; i++){
        cin >> a[i].u >> a[i].v >> a[i].w;
    } 
    sort(a, a + m, cmp);
    for(int i = 0; i <n; i++){
        fa[i] = i;
    }
    int tot = 0;
    for(int i = 0; i < m; i++){
        if(find(a[i].u) != find(a[i].v)){
            merge(a[i].u, a[i].v);
            tot += a[i].w;
        }
    }
    cout << tot;
    return 0;
 } 

我知道要输出orz,but,我不知道怎么输出

@Laugh_at_the_sky


by wa_wa_wa_wa @ 2024-07-27 13:48:41

@zp20120123 kruskal每加一条边就让 cnt++ 最后判断cnt是否等于n-1就可以了


by wa_wa_wa_wa @ 2024-07-27 13:56:18

求互关qwq


by zp20120123 @ 2024-07-27 14:03:45

谢谢


by zp20120123 @ 2024-07-27 15:30:19

@wa_wa_wa_wa 我已过关,thank you!


by zhaoyonghao @ 2024-07-31 10:43:38

只要判断cnt==n-1就OK了


by zhaoyonghao @ 2024-07-31 10:44:34

我就这样写的


|