黄色的MST板子，真香~~~直接累加所有边权之后跑一边Kruskal，减掉MST重量即可
参考代码如下：
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 struct node 5 { 6 int u,v,w; 7 }; 8 node f[200001]; 9 bool cmp(node a,node b) 10 { 11 return a.w<b.w; 12 } 13 int n,m,parent[5005],weight,num,sum; 14 int find(int x) 15 { 16 if(parent[x]==x)return x; 17 else return parent[x]=find(parent[x]); 18 } 19 void Union(int R1,int R2) 20 { 21 int r1=find(R1),r2=find(R2); 22 parent[r1]=r2; 23 } 24 int main() 25 { 26 cin>>n>>m; 27 for(int i=1;i<=n;i++)parent[i]=i; 28 for(int i=1;i<=m;i++) 29 { 30 cin>>f[i].u>>f[i].v>>f[i].w; 31 sum+=f[i].w; 32 } 33 sort(f+1,f+m+1,cmp); 34 for(int i=1;i<=m;i++) 35 { 36 int u=find(f[i].u),v=find(f[i].v); 37 if(u!=v) 38 { 39 num++; 40 weight+=f[i].w; 41 Union(u,v); 42 } 43 if(num==n-1)break; 44 } 45 cout<<sum-weight; 46 return 0; 47 }