21pts求调(Kruskal)

My_Xuan @ 2023-08-10 22:38:13

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

int f[5005], n, m, ans, x, y, cnt;
struct eg { int u, v, w; }
a[200005];

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

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

int main ( )
{
    ios :: sync_with_stdio (0); cin.tie (0);
    for (int i = 1; i <= n; i++) f[i] = i;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> a[i].u >> a[i].v >> a[i].w;
    sort (a + 1, a + m + 1, cmp);
    for (int i = 1; i <= m; i++)
    {
        x = find (a[i].u), y = find (a[i].v);
        if (x == y) continue;
        ans += a[i].w, f[y] = x, cnt++;
        if (cnt == n - 1) {cout << ans; return 0;}
    }
    cout << "orz";
    return 0;
}

by Lysea @ 2023-08-10 23:09:18

@My_Xuan 改两个地方：

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

int f[5005], n, m, ans, x, y, cnt;
struct eg { int u, v, w; }
a[200005];

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

int find (int x)
{
    if (f[x] != x) return f[x] = find (f[x]);//here
    return x;
}

int main ( )
{
    ios :: sync_with_stdio (0); cin.tie (0);
    //here
    cin >> n >> m;for (int i = 1; i <= n; i++) f[i] = i;
    for (int i = 1; i <= m; i++)
        cin >> a[i].u >> a[i].v >> a[i].w;
    sort (a + 1, a + m + 1, cmp);
    for (int i = 1; i <= m; i++)
    {
        x = find (a[i].u), y = find (a[i].v);
        if (x == y) continue;
        ans += a[i].w, f[y] = x, cnt++;
        if (cnt == n - 1) {cout << ans; return 0;}
    }
    cout << "orz";
    return 0;
}