最后一个测试点WA，帮忙看一下判断orz的部分

Light_LE @ 2024-10-19 15:43:01

#include <bits/stdc++.h>
#define maxn 200005
using namespace std;
struct Edge {
    int u, v, w;
}edge[maxn];
int n, m, fa[5003], cnt/*判断图是否连通*/, ans;
bool cmp(Edge x, Edge y) {
    return x.w < y.w;
}
int get(int x) {
    if (x == fa[x]) {
        return x;
    }
    return fa[x] = get(fa[x]);
}
bool kruskal() {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    sort(edge + 1, edge + m + 1, cmp);
    for (int i = 1; i <= m; i++) {
        int x = get(edge[i].u), y = get(edge[i].v);
        if (x == y) {
            continue;
        }
        fa[x] = y;
        ans += edge[i].w;

        if (cnt++ == n - 1) {// 利用生成树的定义判断图是否连通
            return 0;
        }
    }
    return 1;// 正确得到结果
}
int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edge[i].u = u, edge[i].v = v, edge[i].w = w;
    }

    if (kruskal()) {
        cout << ans;
    }
    else {
        cout << "orz";
    }
    return 0;
}

by panda791130 @ 2024-10-19 21:53:29

已解决

bool kruskal() {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    sort(edge + 1, edge + m + 1, cmp);
    for (int i = 1; i <= m; i++) {
        int x = get(edge[i].u), y = get(edge[i].v);
        if (x == y) {
            continue;
        }
        fa[x] = y;
        ans += edge[i].w;

        cnt++;
    }
    if(cnt != n - 1){
        return 0;
    }
    return 1;// 正确得到结果
}

即可，尽量不要用cnt++==1之类的东西炫技，操作语句不要放在判断里面

by zhuyanxi @ 2024-10-19 21:57:56

#include <bits/stdc++.h>
#define maxn 200005
using namespace std;
struct Edge {
    int u, v, w;
}edge[maxn];
int n, m, fa[5003], cnt/*判断图是否连通*/, ans;
bool cmp(Edge x, Edge y) {
    return x.w < y.w;
}
int get(int x) {
    if (x == fa[x]) {
        return x;
    }
    return fa[x] = get(fa[x]);
}
bool kruskal() {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    sort(edge + 1, edge + m + 1, cmp);
    for (int i = 1; i <= m; i++) {
        int x = get(edge[i].u), y = get(edge[i].v);
        if (x == y) {
            continue;
        }
        fa[x] = y;
        ans += edge[i].w;

        if (cnt++ == n - 1) {// 利用生成树的定义判断图是否连通
            return 1;
        }
    }
    if (cnt == n - 1) {// 利用生成树的定义判断图是否连通
        return 1;
    }
    else{
        return 0;
    }
}
int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edge[i].u = u, edge[i].v = v, edge[i].w = w;
    }

    if (kruskal()) {
        cout << ans;
    }
    else {
        cout << "orz";
    }
    return 0;
}

by Light_LE @ 2024-10-20 09:31:56

thx