prim算法模板

图论 C++ 公开

#include <bits/stdc++.h>
using namespace std;

const int N = 510;
const int INF = 0x3f3f3f3f;

int n, m;           // n个点，m条边
int g[N][N];         // 邻接矩阵存图
int dist_[N];        // 存储每个点到"当前最小生成树"的最短距离
bool st[N];           // 标记点是否已加入生成树

int prim() {
    memset(dist_, 0x3f, sizeof dist_);
    int res = 0; // 最小生成树的总权值

    for (int i = 0; i < n; i++) {
        int t = -1;
        // 1. 在还未加入树的点中，找距离树最近的点t
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist_[j] < dist_[t]))
                t = j;

        // 如果找到的点距离仍是INF，说明图不连通
        if (i && dist_[t] == INF) return INF;

        // 2. 累加答案（注意：第一个点不累加，因为dist_[起点]初始不代表边权）
        if (i) res += dist_[t];

        // 3. 用点t更新其他点到集合的距离
        for (int j = 1; j <= n; j++)
            dist_[j] = min(dist_[j], g[t][j]);

        // 4. 标记t已加入树
        st[t] = true;
    }
    return res;
}

int main() {
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);

    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = min(g[u][v], w); // 处理重边，取最小值
    }

    int t = prim();
    if (t == INF) cout << "impossible" << endl;
    else cout << t << endl;

    return 0;
}