题解

最小生成树水题。要让去除的 $\sum f(i,j)$ 最大，因为总和 $\sum_{i=1}^{m}f(i,j)$ 固定，所以只需要让保留的 $\sum f(i,j)$ 最小即可，从而转换成为最小生成树问题。

#include<bits/stdc++.h>
using namespace std;
struct node{
    int u,v,w;
}t;
int n,m;
vector<node>v;
int pa[105];
int find(int x){
    if(pa[x]==x)return x;
    return pa[x]=find(pa[x]);
}
//Kruskal
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)pa[i]=i;
    while(m--){
        cin>>t.u>>t.v>>t.w;
        v.push_back(t);
    }
    sort(v.begin(),v.end(),[](const node&a,const node&b){return a.w<b.w;});
    int ans=0;
    for(auto i:v){
        int u=find(i.u),v=find(i.v);
        if(u!=v)pa[v]=u;
        else ans+=i.w;
    }
    cout<<ans;
    return 0;
}