AcWing 1141. 局域网
原题链接
简单
作者:
Kuro.
,
2024-01-10 15:44:05
,
所有人可见
,
阅读 42
/*
被去除网线f(i,j)之和最大 == 连通块中的网线总f(i,j)最小 -> 最小生成树问题
Kruskal 算法
1.将所有边权从小到大排序
2.依次枚举每条边a,b,w
·如果a和b不连通
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100,M =210;
int n,m;
struct Edge{
int a,b,w;
bool operator< (const Edge &t)const{
return w<t.w;
}
}e[M];
int p[N];
int find(int x){
if (p[x]!=x) p[x]=find(p[x]);
return p[x];
}
/*
Kruskal 算法
1. 将所有边按权重从小到大排序 O(mlogm)
2. 枚举每条边 a->b 权重c,
如果a,b不连通:将这条边加入集合中
*/
int main(){
cin>>n>>m;
int num=0;
for (int i=1;i<=n;i++) p[i]=i;
for (int i=0;i<m;i++){
int a,b,w;
cin>>a>>b>>w;
num+=w;
e[i] = {a,b,w};
}
sort(e,e+m);
int res = 0;
for (int i = 0;i<m;i++){
int a = find(e[i].a),b = find(e[i].b),w = e[i].w;
//如果不连通将这条边加入到集合中,res表示最小生成树的边权和
if (a!=b){
res+=w;
p[a] = b;
}
}
//总边权和-最小生成树的权和 = 被去除网线的最大权值
cout<<num-res<<endl;
return 0;
}