【普及】最小生成树

0

liangsheng LV 3 SU @ 2025-12-12 17:05:27

完整版并查集，路径压缩 + 启发式合并
时间复杂度： $O(m \times log(m) + m)$
期望得分：100

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

struct Node {
    int u, v, w;
};

// 并查集(Union-Find Disjoint Sets/DSU)
struct DSU {
    int n;
    vector<int> f, sz;

    DSU(int N): n(N) {
        // 将 f 的 size 设置为 n + 1
        f.resize(n + 1);

        // 相当于 for (int i = 0; i <= n; i++) f[i] = i;
        // 将从 0 开始的一段连续的数赋值给 f.begin() 到 f.end()
        iota(f.begin(), f.end(), 0);

        // 将 sz 的 size 设置为 n + 1, 并初始化为 1
        sz.assign(n + 1, 1);

        // 对于 vector 的初始化
        // 如果只需要设置 size, 不需要设置初值, 用 resize
        // 如果既需要设置 size, 也需要设置初值, 用 assign
    }

    // 递归写法, 更清晰, 建议使用
    int find(int x) {
        return f[x] == x ? f[x] : f[x] = find(f[x]);
    }

    // 判断 x, y 是否在同一集合
    bool same(int x, int y) {
        return find(x) == find(y);
    }

    // 合并 x, y, 返回合并后的根
    int merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return x;
        // 将 sz小的 合并到 sz大的
        if (sz[x] < sz[y]) swap(x, y);
        sz[x] += sz[y], f[y] = x;
        return x;
    }

    // 返回 x 所在的集合的大小
    int size(int x) {
        return sz[find(x)];
    }
};

int kruskal(int n, int m, vector<Node>& g) {
    // 按边权从小到大排序
    sort(g.begin(), g.end(), [&](const Node& x, const Node& y) {
        return x.w < y.w;
    });
    
    int cnt = 0;  // 已经选的边数
    int ans = 0;  // 当前选的边的权值和
    DSU dsu(n);   // 并查集, 注意传入节点个数
    for (int i = 0; i < m; i++) {
        int u = g[i].u, v = g[i].v, w = g[i].w;
        
        // 如果 u, v 不联通, 就添加边, 并且合并 u, v
        if (!dsu.same(u, v)) {
            ans += w, cnt++;
            dsu.merge(u, v);
        }

        // 只需要 n - 1 条边
        if (cnt == n - 1) break;
    }
    if (cnt != n - 1) return -1;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;
    
    vector<Node> g(m);
    for (int i = 0; i < m; i++) cin >> g[i].u >> g[i].v >> g[i].w;

    int ans = kruskal(n, m, g);
    if (ans == -1) cout << "orz" << '\n';
    else cout << ans << '\n';

    return 0;
}

0

liangsheng LV 3 SU @ 2025-12-12 17:04:17

并查集，不带路径压缩
时间复杂度： $O(m \times log(m) + m \times log(n))$
期望得分：100

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

struct Node {
    int u, v, w;
};

struct DSU {
    int n;
    vector<int> f;   // 每个点的编号
    vector<int> sz;  // 每个编号的节点个数
    
    DSU(int N): n(N) {
        // 初始都是 i
        f.assign(n + 1, 0);
        for (int i = 1; i <= n; i++) f[i] = i;
        
        // 初始节点数都是 1
        sz.assign(n + 1, 1);
    } 
    
    int find(int x) {
        while (f[x] != x) x = f[x];
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);    
    }
    
    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return ;  // 已经是同一编号
        
        // 将 sz小的 合并到 sz大的
        if (sz[x] < sz[y]) swap(x, y);
        sz[x] += sz[y], f[y] = x;
    }
};

int kruskal(int n, int m, vector<Node>& g) {
    
    // 按边权从小到大排序
    sort(g.begin(), g.end(), [&](const Node& x, const Node& y) {
        return x.w < y.w;
    });
    
    // cnt: 已经选的边数, ans: 当前选的边的权值和
    int cnt = 0, ans = 0;          
    DSU dsu(n);
    for (int i = 0; i < m; i++) {
        int u = g[i].u, v = g[i].v, w = g[i].w;
        
        // 现在要判断 u, v 是否已经联通
        if (dsu.same(u, v)) continue;  // 已经联通
        else {
            // u, v 不联通, 要这条边
            ans += w;
            if (++cnt == n - 1) break;  // 已经选 n-1 条边
            
            // 把所有和 v 联通的点的编号, 都改为 f[u]
            dsu.merge(u, v);
        }
    }
    if (cnt != n - 1) return -1;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    vector<Node> g(m);
    for (int i = 0; i < m; i++) cin >> g[i].u >> g[i].v >> g[i].w;
    
    int ans = kruskal(n, m, g);
    if (ans == -1) cout << "orz" << '\n';
    else cout << ans << '\n';
    
    return 0;
}

0

liangsheng LV 3 SU @ 2025-12-12 17:02:38

合并 vector<int> 时，将点数少的合并到点数多的
这种思想叫 $\color{orange}{\textbf{启发式合并}}$
时间复杂度： $O(m \times log(m) + m \times log(n))$
期望得分：100

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

struct Node {
    int u, v, w;
};

int kruskal(int n, int m, vector<Node>& g) {
    
    // 按边权从小到大排序
    sort(g.begin(), g.end(), [&](const Node& x, const Node& y) {
        return x.w < y.w;
    });
    
    // cnt: 已经选的边数, ans: 当前选的边的权值和
    int cnt = 0, ans = 0;          
    
    vector<int> f(n + 1);
    vector<vector<int>> t(n + 1);  // t[i]: 编号为 i 的点集
    for (int i = 1; i <= n; i++) f[i] = i, t[i].push_back(i);
    
    for (int i = 0; i < m; i++) {
        int u = g[i].u, v = g[i].v, w = g[i].w;
        
        // 现在要判断 u, v 是否已经联通
        if (f[u] == f[v]) continue;  // 已经联通
        else {
            // u, v 不联通, 要这条边
            ans += w;
            if (++cnt == n - 1) break;  // 已经选 n-1 条边
            
            // 把所有和 v 联通的点的编号, 都改为 f[u]
            if ((int) t[f[u]].size() < (int) t[f[v]].size()) swap(u, v);
            int fv = f[v];
            for (int x : t[fv]) {
                t[f[u]].push_back(x);
                f[x] = f[u];
            }
            t[fv].clear();
        }
    }
    if (cnt != n - 1) return -1;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    vector<Node> g(m);
    for (int i = 0; i < m; i++) cin >> g[i].u >> g[i].v >> g[i].w;
    
    int ans = kruskal(n, m, g);
    if (ans == -1) cout << "orz" << '\n';
    else cout << ans << '\n';
    
    return 0;
}

0

liangsheng LV 3 SU @ 2025-12-12 17:00:49

将同一编号的点用 vector<vector<int>> 存起来
同一编号时，遍历对应的 vector 就行
时间复杂度： $O(m \times log(m) + m \times n)$
期望得分：70

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

struct Node {
    int u, v, w;
};

int kruskal(int n, int m, vector<Node>& g) {
    
    // 按边权从小到大排序
    sort(g.begin(), g.end(), [&](const Node& x, const Node& y) {
        return x.w < y.w;
    });
    
    // cnt: 已经选的边数, ans: 当前选的边的权值和
    int cnt = 0, ans = 0;          
    
    vector<int> f(n + 1);
    vector<vector<int>> t(n + 1);  // t[i]: 编号为 i 的点集
    for (int i = 1; i <= n; i++) f[i] = i, t[i].push_back(i);
    
    for (int i = 0; i < m; i++) {
        int u = g[i].u, v = g[i].v, w = g[i].w;
        
        // 现在要判断 u, v 是否已经联通
        if (f[u] == f[v]) continue;  // 已经联通
        else {
            // u, v 不联通, 要这条边
            ans += w;
            if (++cnt == n - 1) break;  // 已经选 n-1 条边
            
            // 把所有和 v 联通的点的编号, 都改为 f[u]
            int fv = f[v];
            for (int x : t[fv]) {
                t[f[u]].push_back(x);
                f[x] = f[u];
            }
            t[fv].clear();
        }
    }
    if (cnt != n - 1) return -1;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    vector<Node> g(m);
    for (int i = 0; i < m; i++) cin >> g[i].u >> g[i].v >> g[i].w;
    
    int ans = kruskal(n, m, g);
    if (ans == -1) cout << "orz" << '\n';
    else cout << ans << '\n';
    
    return 0;
}

0

liangsheng LV 3 SU @ 2025-12-12 16:58:55

为每个点选取一个编号
选边的时候，将编号暴力统一
时间复杂度： $O(m \times log(m) + m \times n)$
期望得分：50

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

struct Node {
    int u, v, w;
};

int kruskal(int n, int m, vector<Node>& g) {
    
    // 按边权从小到大排序
    sort(g.begin(), g.end(), [&](const Node& x, const Node& y) {
        return x.w < y.w;
    });
    
    int cnt = 0;           // 已经选的边数
    int ans = 0;           // 当前选的边的权值和
    vector<int> f(n + 1);  // 编号
    for (int i = 1; i <= n; i++) f[i] = i;
    
    for (int i = 0; i < m; i++) {
        int u = g[i].u, v = g[i].v, w = g[i].w;
        
        // 现在要判断 u, v 是否已经联通
        if (f[u] == f[v]) continue;  // 已经联通
        else {
            // u, v 不联通, 要这条边
            ans += w;
            if (++cnt == n - 1) break;  // 已经选 n-1 条边
            
            // 把所有和 v 联通的点的编号, 都改为 f[u]
            int fv = f[v];
            for (int j = 1; j <= n; j++) {
                if (f[j] == fv) f[j] = f[u];
            }
        }
    }
    if (cnt != n - 1) return -1;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    vector<Node> g(m);
    for (int i = 0; i < m; i++) cin >> g[i].u >> g[i].v >> g[i].w;
    
    int ans = kruskal(n, m, g);
    if (ans == -1) cout << "orz" << '\n';
    else cout << ans << '\n';

    return 0;
}

5 条题解

信息

状态

开发

支持

关于