C++ 并查集解决连边游戏最小成本问题

可以使用并查集来解决这个问题。

首先，我们需要定义一个边的结构体 Edge，包含起点、终点和边的价格。

然后，我们需要定义一个并查集类 UnionFind，用于处理点的连通性。

在并查集类中，我们需要实现以下几个方法：

初始化方法 init(int n)：初始化并查集，将每个点的父节点指向自己。
查找方法 find(int x)：查找点 x 的根节点。
合并方法 merge(int x, int y)：将点 x 和点 y 所在的连通分量合并。
判断方法 isConnected(int x, int y)：判断点 x 和点 y 是否在同一个连通分量中。

接下来，我们可以按照题目给出的操作顺序，依次执行连边操作，并更新并查集。

具体步骤如下：

初始化并查集，将每个点的父节点指向自己。
按照给定的操作顺序，依次执行连边操作，并更新并查集。
统计所有边的价格，并将其排序。
依次选取边，如果边的起点和终点不在同一个连通分量中，则选择该边，并将起点和终点合并。
继续选取下一条边，直到所有点都联通为止。
返回选取的边的价格总和。

下面是使用 C++ 实现的代码：

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

using namespace std;

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

class UnionFind {
private:
    vector<int> parent;
public:
    void init(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

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

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

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

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

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.w < b.w;
    });

    UnionFind uf;
    uf.init(n);

    int minCost = 0;
    for (const auto& edge : edges) {
        if (!uf.isConnected(edge.u, edge.v)) {
            uf.merge(edge.u, edge.v);
            minCost += edge.w;
        }
    }

    cout << minCost << endl;

    return 0;
}

该算法的时间复杂度为 O(mlogm + mlogn)，其中 m 是操作次数，n 是点的数量。