【小码匠自习室】最小生成树（kruskal）完结撒花

#include <bits/stdc++.h>
using namespace std;
#define endl '\n';

struct edge {
    int weight;
    int from;
    int to;
};

struct cmp {
    bool operator() (const edge &a, const edge &b) {
        return a.weight > b.weight;
    }
};

struct UF {
    vector<int> fa;

    UF (int n) :
        fa(n) {}

    void initialize (int n) {
        for (int i = 0; i < n; ++i) {
            fa[i] = i;
        }
    }

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

    void unite(int x, int y) {
        int a = find(x);
        int b = find(y);
        if (a != b) {
            fa[b] = a;
        }
    }

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

void best_coder() {
    int n;
    cin >> n;
    priority_queue <edge, vector<edge>, cmp> g;
    UF uf(n);
    uf.initialize(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int a;
            cin >> a;
            if (j <= i) {
                continue;
            }
            g.push({a, i, j});
        }
    }
    int ans = 0;
    while (!g.empty()) {
        int a = g.top().from;
        int b = g.top().to;
        if (uf.is_same(a, b)) {
            g.pop();
            continue;
        }
        uf.unite(a, b);
        ans += g.top().weight;
        g.pop();
    }
    cout << ans;
}

void happy_coder() {
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}