样例过了但是全WA

P3366 【模板】最小生成树

星弈小朋友 @ 2023-10-24 21:03:44

大佬看看orz

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1145141;
long long ans,fa[maxn], n, m;

struct node{
    int u,v,w;
}e[maxn];

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

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

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        fa[i] = i;

    for (int i = 1;i <= m; i++)
        cin >> e[i].u >> e[i].v >> e[i].w;
    sort (e + 1, e + 1 + n, cmp);
    int cnt = 0;
    for (int i = 1; i <= m; i ++)
    {
        if (cnt >= n - 1) break;
        int fu = find(e[i].u);
        int fv = find(e[i].v);
        if (fu != fv) 
        {
            fa[fu] = fv;
            ans += e[i].w;
            cnt ++;
        }
    }
    if (ans == 0) cout << "orz";
    else cout << ans;
    return 0;
}

by only_a_speaker @ 2023-10-24 21:13:56

您好,在对边进行排序时,需要对 m 条边进行排序。


by 星弈小朋友 @ 2023-10-26 19:34:28

@only_a_speaker 谢谢巨佬,已AC


|