题目链接

Agri-Net POJ - 1258

思路

$$ 最小生成树模板题，越是简单的题越要注意\\\\是不是多组数据,数组开多大！ $$

时间复杂度

$$ O((N^2)log(N^2)) $$

代码

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

class DSU {
public:
    vector<int> p, r;

    void init(int n) {
        p.resize(n + 10);
        r.resize(n + 10);
        for (int i = 0; i <= n; i++) {
            p[i] = i;
            r[i] = 0;
        }
    }

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

    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }

        if (r[x] < r[y]) {
            p[x] = y;
        } else {
            p[y] = x;
            if (r[x] == r[y]) {
                r[x]++;
            }
        }
        return true;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

DSU dsu;

const int MAXN = 110;
int n;
int a[MAXN][MAXN], id[MAXN * MAXN];

bool cmp(int x, int y) {
    return a[x / n][x % n] < a[y / n][y % n];
}

int main() {
    while (~scanf("%d", &n)) {
        dsu.init(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &a[i][j]);// don't forget &
                id[i * n + j] = i * n + j;
            }
        }
        sort(id, id + n * n, cmp);
        long long ans = 0;
        for (int i = 0; i < n * n; i++) {
            int x = id[i];
            if (!dsu.same(x / n, x % n)) {
                ans += a[x / n][x % n];
                dsu.unite(x / n, x % n);
            }
        }
        printf("%lld\n", ans);
    }

    return 0;
}