C++ 连边游戏最小代价算法：并查集优化

C++ 解决连边游戏最小代价问题

何老板在玩一款连边游戏，游戏地图上有 n 个点围成一个圆圈，点编号 0,...,n。玩家需要执行 m 次操作，每次操作会给出三个整数 x, y, z，需要在点之间连边。在完成所有操作后，需要选择若干条边，使得所有点都联通，并且所选边的价格总和最小。

问题: 如何计算这个最小值？

算法: 可以使用并查集 (Union Find) 算法来解决这个问题。

步骤:

初始化: 创建一个大小为 n 的数组 parent，用于记录每个点的父节点。初始时，每个点的父节点都是自己，即 parent[i] = i。
遍历操作: 按照给定的操作，依次将边加入到连边图中。对于每一次操作，我们需要执行以下步骤：
- 查找根节点: 找到 x 的根节点 rx 和 y 的根节点 ry，可以通过递归地调用 find 函数来实现。
  
  cpp int find(int x) { if (parent[x] == x) { return x; } else { parent[x] = find(parent[x]); // 路径压缩 return parent[x]; } }
- 合并集合: 如果 rx 不等于 ry，说明 x 和 y 不在同一个连通分量中。我们将 rx 的父节点设为 ry，即 parent[rx] = ry。
  
  同时，我们需要将 rx 到 ry 的边的价格加入到连边图中。我们可以使用一个额外的数组 cost，用于记录每个连边的价格。初始时，cost 的所有元素都是无穷大。在连接 rx 和 ry 的边上，我们更新 cost[rx] 和 cost[ry] 为 z 的值。
计算最小代价: 重复步骤 2，直到完成所有操作。最后，我们遍历连边图中的所有边，将所有点连接起来，并计算连接边的价格总和。最小的总和即为所求的答案。

时间复杂度: 整个算法的时间复杂度为 O(n + m * α(n))，其中 α(n) 是 Ackermann 函数的反函数，接近于常数。

**示例代码:**cpp#include #include #include

using namespace std;

const int INF = 1e9;

int find(int x, vector& parent) { if (parent[x] == x) { return x; } else { parent[x] = find(parent[x]); return parent[x]; }}

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

vector<int> parent(n);    for (int i = 0; i < n; ++i) {        parent[i] = i;    }

vector<int> cost(n, INF);    for (int i = 0; i < m; ++i) {        int x, y, z;        cin >> x >> y >> z;

    int rx = find(x, parent);        int ry = find(y, parent);

    if (rx != ry) {            parent[rx] = ry;            cost[rx] = min(cost[rx], z); // 更新边的价格            cost[ry] = min(cost[ry], z);        }    }

long long totalCost = 0;    for (int i = 0; i < n; ++i) {        totalCost += cost[i];    }

cout << totalCost << endl;    return 0