题目传送门

黄色的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 }

View Code

 

 

 

　　

版权声明：本文为szmssf原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/szmssf/p/10997388.html