思路

用 Kr 算法，把树里所有边权的和，再被整个图的总边权和减掉就是答案了

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 105,M = 5055,INF = 0x3fffffff;

// 链式前向星 
struct edge{
	int u,v,w,prev;
}edges[M];
int tot,tail[N];
void add_edge(int u,int v,int w){
	edges[++tot] = {u,v,w,tail[u]};
	tail[u] = tot;
}

int fa[N],summ,sum;
int find(int x){
	if (x == fa[x])	return x;
	return fa[x] = find(fa[x]);
}
void merge(int x,int y){
	fa[find(y)] = find(x);
}
bool cmp(edge b,edge c){
	return b.w < c.w;
}
int main(int argc, char **argv){
//	freopen("net.in","r",stdin);
//	freopen("net.out","w",stdout);
	for (int i = 0;i < N;i++)	fa[i] = i;
	int n,m;
	cin >> n >> m;
	for (int i = 0;i < m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		summ += w;
		add_edge(u,v,w);
	}
	sort(edges + 1,edges + m + 1,cmp);
	for (int i = 1;i <= tot;i++){
		int u = edges[i].u,v = edges[i].v,w = edges[i].w;
		if (find(u) == find(v))	continue;
		sum += w;
		merge(u,v);
	}
	cout << summ - sum;
	return 0;
}

上一道题改一改

#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int MAX_INT=0x3fffffff;
const int MAX_A=2e5;
vector<pair<int,int>> arr[MAX_A];
int n,m,ss,f[MAX_A],ans;
bool vis[MAX_A];
priority_queue<pair<int,int>> q;
signed main(){
    cin>>n>>m;
    fill(f,f+n+10,MAX_INT);
    int sum=0;//这里
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        arr[a].push_back({b,c});
        arr[b].push_back({a,c});
        sum+=c;//这里
    }
    f[1]=0;
    q.push({0,1});
    while(q.size()){
            pair<int,int> ff=q.top();
            q.pop();
            int d=ff.second;
            if(vis[d]) continue;
            ans+=-ff.first;
            vis[d]=1;
            int len=arr[d].size();
            for(int j=0;j<len;j++){
                int b=arr[d][j].first;
                int a=arr[d][j].second;
                if(f[b]>a){
                    f[b]=a;
                    q.push({-f[b],b});
                }
            }
    }
    cout<<sum-ans;//这里
    return 0;
}

速通

思路： 先用prim or kruskal求最小生成树边权和，再用总边权和减去它即可 代码见上一题