WA on #13

Pollococido @ 2024-07-10 22:55:36

#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) return 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, point = 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;
            point++;
            if (point == n - 1) break;
        }
    }

    if (point != n - 1) cout << "orz";
    cout << res;
    return 0;
}

by Pollococido @ 2024-07-10 22:58:18

悬关

by keep_shining @ 2024-07-11 06:30:01

@Pollococido

#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) return 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, point = 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;
            point++;
            if (point == n - 1) break;
        }
    }

    if (point != n - 1) cout << "orz";
    cout << res;//这里要加else
    return 0;
}

by Pollococido @ 2024-07-11 06:56:41

@keep_shining 已关