c++ Prim

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

typedef pair<int, int> PII;
#define fi first
#define se second
const int M=205;
const int N=105;
int n, m;
bool vis[N];
int dist[N];
vector<PII> g[N];

int prim(){
    dist[1]=0;
    int ans=0;
    for(int i=0; i<n; ++i){
        int node=-1;
        for(int j=1; j<=n; ++j){
            if(!vis[j] && (node==-1 || dist[j]<dist[node])) node=j;
        }
        if(node==-1) break;
        vis[node]=true;
        if(dist[node]<0x3f3f3f3f) ans+=dist[node]; // 处理图中连通分量数量超过1个, 略过不连通的情况
        for(auto &e: g[node]){
            dist[e.fi]=min(dist[e.fi], e.se);
        }
    }
    return ans;
}


int main(){
    memset(vis, 0x00, sizeof vis);
    memset(dist, 0x3f, sizeof dist);
    cin>>n>>m;
    int ans=0;
    while(m--){
        int x, y, z;
        cin>>x>>y>>z;
        g[x].push_back({y, z});
        g[y].push_back({x, z});
        ans+=z;
    }

    cout<<ans-prim()<<endl;

    return 0;
}

c++ Kruskal

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

const int M=205;
const int N=105;
int n, m, ans=0;

struct Edge{
    int a, b, w;
    Edge(int _a, int _b, int _w):a(_a), b(_b), w(_w){};
    bool operator< (const Edge &o) const{
        return w<o.w;
    }
};

vector<Edge> g;
int fa[N];


inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

void kruskal(){
    sort(g.begin(), g.end());
    for(Edge &e: g){
        int x=e.a;
        int y=e.b;
        if(find(x)!=find(y)){
            fa[find(x)]=find(fa[y]);
        }
        else ans+=e.w;
    }
}

int main(){
    cin>>n>>m;
    for(int i=1; i<=n; ++i) fa[i]=i;
    while(m--){
        int x, y, z;
        cin>>x>>y>>z;
        g.push_back({x, y, z});
    }

    kruskal();
    cout<<ans<<endl;

    return 0;
}