prim求最小生成树方法

prim算法要求所有点在同一个连通块内，因此本题可以逐个连通块用prim算法。

其中tot表示所有边的总长度，res表示加入生成树中边的长度，ans = tot - res。

每次进行一次prim会将该连通块内的点全部标记为true，枚举没被标记过的点进行prim即可。

代码：

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

typedef pair<int, int> PII;

int g[N][N], n, m, tot, dist[N], res;

bool st[N];

void prim(int u) {
    priority_queue<PII, vector<PII>, greater<PII>> q;
    dist[u] = 0;
    q.push({0, u});
    while (!q.empty()) {
        auto t = q.top();
        q.pop();
        int ver = t.second;
        if (st[ver]) continue;
        st[ver] = true;
        res += dist[ver];
        for (int i = 1; i <= n; i++) {
            if (dist[i] > g[ver][i]) {
                dist[i] = g[ver][i];
                q.push({dist[i], i});
            }
        }
    }
}

int main() {
    cin >> n >> m;
    memset(dist, 0x3f, sizeof dist);
    memset(g, 0x3f, sizeof g);
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = c;
        tot += c;
    }
    for (int i = 1; i <= n; i++)
        if (!st[i]) prim(i);
    cout << tot - res << endl;
    return 0;
}