(Prim) $O(n^2)$

一直不怎么用Kruskal 就用的prim 调试的时候发现会有不连通的情况，用并查集找到每个连通块，
互相连一条边权为0的边，求出最小生成树再用所有边的和减去就是答案

C++ 代码

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

const int N = 110, M = 210, INT = 0x3f3f3f3f;

vector<int> fa;
int n, m;
int e[M], ne[M], w[M], h[N], idx;
bool st[N];
int dist[N];
int g[N][N];
int p[N];

void add(int a,int b,int c = 1)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int prim()
{
    int res = 0;
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    for (int i = 0; i < n; i ++ )
    {
        int last =  -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (last == -1 || dist[last] > dist[j]))
                last = j;

        if (i) res += dist[last];
        st[last] = true;

        for (int i = 1; i <= n; i ++ )
            dist[i] = min(dist[i], g[last][i]);
    }
    return res;
}

int find(int u)
{
    if (p[u] != u) p[u] = find(p[u]);
    return p[u];
}

void merge(int a,int b)
{
    p[find(a)] = find(b);
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    memset(g, 0x3f, sizeof g);
    int res = 0;
    while (m --)
    {
        int a, b, c;
        cin >> a >> b>> c;
        res += c;
        merge(a, b);
        g[a][b] = g[b][a] = min(c, g[a][b]);
    }
    for (int i = 1; i <= n; i ++ ) if (p[i] == i) fa.push_back(i);

    for (int i = 0; i < fa.size(); i ++ )
        for (int j = i + 1; j < fa.size(); j ++ )
            g[fa[i]][fa[j]] = g[fa[j]][fa[i]] = 0;

    res -= prim();

    cout << res << endl;
}