最小生成树prime算法

最小生成树是指一棵树，它连接了一个无向连通图的所有节点，且边权值之和最小。其中，prime算法就是一种用于寻找最小生成树的贪心算法。

prime算法的实现过程如下：
1. 任选一个节点作为起点。
2. 找到与该节点相连的所有边中权值最小的边所连接的节点，将其加入生成树中。
3. 重复步骤2，直到所有节点都被加入生成树中。

下面是prime算法的C++代码实现：

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

const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;

int n, m; //n为节点数，m为边数
int head[MAXN], dis[MAXN];
bool vis[MAXN];

struct Edge {
    int to, w, next;
}edge[MAXN * 2];

void addEdge(int u, int v, int w) {
    static int cnt = 0;
    edge[++cnt] = {v, w, head[u]};
    head[u] = cnt;
}

void prim(int s) {
    memset(dis, 0x3f, sizeof(dis)); //初始化dis数组，表示所有节点到当前生成树的距离
    memset(vis, false, sizeof(vis)); //初始化vis数组，表示节点是否已经在生成树中
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; //小根堆
    dis[s] = 0; //起点距离为0
    pq.push({dis[s], s}); //将起点加入小根堆

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue; //如果已经在生成树中，则跳过
        vis[u] = true; //否则标记为已访问
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to;
            if (!vis[v] && edge[i].w < dis[v]) { //如果未访问过且当前边的权值小于dis[v]
                dis[v] = edge[i].w; //更新dis[v]
                pq.push({dis[v], v}); //将v加入小根堆
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w); //因为是无向图，所以要加两条边
    }
    prim(1); //以1号节点为起点
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans += dis[i]; //计算最小生成树的权值和
    cout << ans << endl;
    return 0;
}