最小生成树

Prim

\(O(n\log n)\)

模版

C++
struct Node {
    int to, val;
    Node() = default;
    Node(const int to, const int val) : to(to), val(val) {}
    bool operator<(const Node &x) const {
        return val > x.val;
    }
};
vector<vector<Node>> adj;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    adj.assign(n + 1, vector<Node>());
    for (int i = 0 ; i < m ; i++) {
        int u, v, val;
        cin >> u >> v >> val;
        adj[u].emplace_back(v, val);
        adj[v].emplace_back(u, val);
    }
    vector<int> dist(n + 1, 0x7fffffff), vis(n + 1);
    priority_queue<Node> que;
    que.emplace(1, 0);
    int res = 0;
    int cnt = 0;
    while (!que.empty() && cnt < n) {
        auto [to, val] = que.top();
        que.pop();
        if (vis[to] == true) continue;
        vis[to] = true;
        cnt++;
        res += val;
        for (auto &[to, val] : adj[to]) {
            if (val < dist[to]) {
                dist[to] = val;
                que.emplace(to, val);
            }
        }
    }
    if (cnt != n) {
        cout << "orz\n";
    } else {
        cout << res << "\n";
    }
    return 0;
}

例题

洛谷P3366

P3366 【模板】最小生成树 - 洛谷

Kruskal

\(O(m\log m)\)

模版

C++
struct Node {
    int from, to, val;
    Node() = default;
    Node(const int from, const int to, const int val) : from(from), to(to), val(val) {}
    bool operator<(const Node &x) const {
        return val > x.val;
    }
};
int f[5005];
int find(const int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<Node> edge(m);
    iota(f, f + n + 1, 0);
    priority_queue<Node> que;
    for (int i = 0 ; i < m ; i++) {
        cin >> edge[i].from >> edge[i].to >> edge[i].val;
        que.emplace(edge[i]);
    }
    vector<int> vis(n + 1);
    int res = 0;
    int cnt = 1;
    while (!que.empty() && cnt < n) {
        auto [from, to, val] = que.top();
        que.pop();
        from = find(from);
        to = find(to);
        if (from == to) continue;
        f[from] = to;
        cnt++;
        res += val;
    }
    if (cnt != n) {
        cout << "orz\n";
    } else {
        cout << res << "\n";
    }
    return 0;
}

例题

洛谷P3366

P3366 【模板】最小生成树 - 洛谷

最小异或生成树

例题

CF888G

Problem - G - Codeforces

\(n\) 个点，每个点都有一个 \(a_i\), 点 \(i\) 和 \(j\) 的边的权值等于 \(a_i\oplus a_j\)，问最小生成树的权值(所有边权之和)。

代码

C++
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
int tot = 0;
const int N = 200000 * 31;
vector<int> e[N];
int nxt[N][2];
void insert(int x) {
    int index = 0;
    for (int i = 30 ; i >= 0 ; i--) {
        int k = x >> i & 1;
        if (nxt[index][k] == 0) {
            nxt[index][k] = ++tot;
        }
        index = nxt[index][k];
        e[index].emplace_back(x);
    }
}
int query(int index, int d, int x) {
    if (d < 0) {
        return 0;
    }
    int k = x >> d & 1;
    if (nxt[index][k]) {
        return query(nxt[index][k], d - 1, x);
    }
    return query(nxt[index][k ^ 1], d - 1, x) + (1 << d);
}
long long ans = 0;
void solve(int index, int d) {
    int L = nxt[index][0], R = nxt[index][1];
    if (L && R) {
        if (e[L].size() > e[R].size()) swap(L, R);
        int mi = 1 << 30;
        for (auto &x : e[L]) {
            mi = min(mi, query(R, d - 1, x));
        }
        ans += mi + (1 << d);
    }
    if (L) {
        solve(L, d - 1);
    }
    if (R) {
        solve(R, d - 1);
    }

}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        insert(a[i]);
    }
    solve(0, 30);
    cout << ans << "\n";
    return 0;
}