C++ 最小生成树算法解决连边游戏最小成本问题

何老板在玩一款连边游戏，游戏虽然简单，他仍旧乐此不疲。游戏地图上有 n 个点围成一个圆圈，点编号 0,...,n。接下来玩家要执行 m 次操作。

对于其中第 i 次操作，会给出三个整数 x y z，玩家需要执行的连边过程如下：

在编号 x+0 与 y+0 的点间连边，边的价格 z+0 ;
在编号 y+0 与 x+1 的点间连边，边的价格 z+1 ;
在编号 x+1 与 y+1 的点间连边，边的价格 z+2 ;
在编号 y+1 与 x+2 的点间连边，边的价格 z+3 ;
在编号 x+2 与 y+2 的点间连边，边的价格 z+4 ;
在编号 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，请选择时间复杂度较低的算法

这个问题可以使用最小生成树算法来解决。最小生成树是指在一个连通图中选择一些边，使得这些边连接所有的节点，并且总权值最小。

在这个问题中，我们可以将每一个点看作一个节点，将每一次操作得到的边看作图中的边，边的权值就是操作给出的价格。最后我们需要选择一些边，使得所有的点都联通，并且所选边的价格总和最小。

具体的算法如下：

创建一个包含 n 个节点的图。
对于每一次操作，根据给出的 x、y 和 z，将编号为 x 和 y 的点之间连边，并且边的权值为 z。注意对于边的连接，要考虑到编号是在模 n 意义下的。
使用最小生成树算法（如 Prim 算法或 Kruskal 算法）找到最小生成树，并计算所选边的价格总和。

这个算法的时间复杂度为 O(mlogn)，其中 m 为操作的次数，n 为点的个数。因为在步骤 2 中需要对每一次操作进行边的添加，所以总共需要进行 m 次操作，而在步骤 3 中需要使用最小生成树算法，其时间复杂度为 O(mlogn)。

下面是一个使用 Prim 算法实现上述算法的示例代码：

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct Edge {
    int to;
    int weight;
};

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<Edge>> graph(n);
    
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        
        x %= n;
        y %= n;
        
        graph[x].push_back({y, z + i});
        graph[y].push_back({x, z + i + 1});
    }
    
    vector<bool> visited(n, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    long long totalWeight = 0;
    
    // Start with node 0
    visited[0] = true;
    for (const auto& edge : graph[0]) {
        pq.push({edge.weight, edge.to});
    }
    
    while (!pq.empty()) {
        auto [weight, node] = pq.top();
        pq.pop();
        
        if (visited[node]) {
            continue;
        }
        
        visited[node] = true;
        totalWeight += weight;
        
        for (const auto& edge : graph[node]) {
            pq.push({edge.weight, edge.to});
        }
    }
    
    cout << totalWeight << endl;
    
    return 0;
}

在这个示例代码中，我们使用了一个邻接表来表示图。在步骤 2 中，我们将每一次操作得到的边添加到对应的节点的邻接表中。在步骤 3 中，我们使用了 Prim 算法来找到最小生成树，并计算所选边的价格总和。最后输出结果即为所求的最小值。

希望对你有帮助！