C++ 连边游戏最小总权值计算 - 最小生成树算法 - 常规

何老板在玩一款连边游戏，游戏虽然简单，他仍旧乐此不疲。游戏地图上有 n 个点围成一个圆圈，点编号0,...,n。接下来玩家要执行 m 次操作。对于其中第 i 次操作，会给出三个整数 x y z，玩家需要执行的连边过程如下：第 1 步，在编号 x+0 与 y+0 的点间连边，边的价格 z+0 ; 第 2 步，在编号 y+0 与 x+1 的点间连边，边的价格 z+1 ; 第 3 步，在编号 x+1 与 y+1 的点间连边，边的价格 z+2 ; 第 4 步，在编号 y+1 与 x+2 的点间连边，边的价格 z+3 ; 第 5 步，在编号 x+2 与 y+2 的点间连边，边的价格 z+4 ; 第 6 步，在编号 y+2 与 x+3 的点间连边，边的价格 z+5 ; ...... 在执行完 m 次操作后，游戏会要求玩家选出若干条边，使得所有点都联通，并且所选边的价格总和最小。何老板请你帮忙计算这个最小值。注意：连边时，点的编号是在模 n 意义下的。比如点 n 等价于点 0 对于所有的数据：2≤n≤2∗10^5,1≤m≤2∗10^5,0≤x,y≤n−1,1≤z≤10^9，请选择时间复杂度较低的算法内容：首先，我们可以将问题转化为一个最小生成树的问题。将每个点看作图中的一个节点，每个操作看作图中的一条边，并且每条边的权值即为操作中的 z 值。那么我们需要找到一个最小生成树，使得所有的点都联通。

接下来，我们考虑如何构建这个图。由于点的编号是在模 n 意义下的，我们可以将所有的点都复制一遍，得到 2n 个点。对于每个操作，我们可以将两个点 x 和 y 分别映射到两个不同的节点上，然后将它们之间的边加入图中。这样，我们就得到了一个包含 2n 个点的图。

然后，我们可以使用 Kruskal 算法来求解最小生成树。Kruskal 算法的基本思想是将边按照权值从小到大进行排序，然后依次选取权值最小的边，如果这条边的两个节点不在同一个连通分量中，就将它们合并，并将这条边加入最小生成树中。直到最小生成树中包含了 n 个节点，即所有的点都联通。

在具体实现时，我们可以使用并查集来维护每个节点所属的连通分量。并查集是一个用于处理集合合并与查询问题的数据结构，它提供了合并两个集合和查询一个元素所属的集合的操作。对于每次操作，我们可以先查询两个节点所属的集合，然后将它们合并。如果两个节点已经在同一个集合中，说明它们之间已经存在一条路径，不需要再进行连边操作。

最后，我们只需要将最小生成树中的边的权值相加，即为所求的答案。

以下是用 C++ 实现的代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 并查集的定义
class UnionFind {
public:
    vector<int> parent;

    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

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

    void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
        }
    }
};

// 边的定义
struct Edge {
    int u;
    int v;
    int weight;

    Edge(int u, int v, int weight) : u(u), v(v), weight(weight) {}
};

// 用于比较边的权值
bool compare(const Edge& e1, const Edge& e2) {
    return e1.weight < e2.weight;
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<Edge> edges;
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        edges.emplace_back(x, y, z);
    }

    // 将所有的点复制一遍，得到 2n 个点
    int totalNodes = 2 * n;
    UnionFind uf(totalNodes);

    // 将边按照权值从小到大进行排序
    sort(edges.begin(), edges.end(), compare);

    int selectedEdges = 0;  // 已选取的边数
    long long totalWeight = 0;  // 总权值

    for (int i = 0; i < m; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int weight = edges[i].weight;

        // 查询 u 和 v 所属的连通分量
        int rootU = uf.find(u);
        int rootV = uf.find(v);

        // 如果 u 和 v 不在同一个连通分量中，将它们合并，并将边的权值加入总权值
        if (rootU != rootV) {
            uf.merge(rootU, rootV);
            selectedEdges++;
            totalWeight += weight;
        }

        // 如果已选取的边数等于 n-1，即所有的点都联通，跳出循环
        if (selectedEdges == n - 1) {
            break;
        }
    }

    cout << totalWeight << endl;

    return 0;
}

由于使用了并查集来维护连通性，该算法的时间复杂度为 O(mα(n))，其中 α(n) 是 Ackermann 函数的反函数，它的增长极其缓慢，可以认为是一个很小的常数。因此，该算法的时间复杂度可以认为是 O(m)。