RE,悬一关

P3366 【模板】最小生成树

Pollococido @ 2024-07-10 21:59:32

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int a, b, w;
}node[200010];
int fa[5010];
int n, m;

bool cmp(Node a, Node b) {
    return a.w < b.w;
}

int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    else return fa[x];
}

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) fa[i] = i;

    for (int i = 1; i <= m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        node[i] = {a, b, w};
    }

    sort(node + 1, node + m + 1, cmp);

    int res = 0;
    for (int i = 1; i <= m; i++) {
        int a = node[i].a, b = node[i].b, w = node[i].w;
        a = find(a), b = find(b);
        if (a != b) {
            fa[a] = b;
            res += w;
        }
    }

    cout << res;
    return 0;
}

by yx666 @ 2024-07-10 22:27:25

@Pollococido

int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    else return fa[x];
}

改成

int find(int x) {
    if (fa[x] != x) return fa[x] = find(fa[x]);
    else return fa[x];
}

by Pollococido @ 2024-07-10 22:44:59

谢dalao,已关 此贴结


|