AcWing 1141. 局域网
原题链接
简单
作者:
Value
,
2020-10-13 09:59:05
,
所有人可见
,
阅读 351
#include <iostream>
#include <algorithm>
using namespace std;
int n, k;
const int N = 210;
typedef long long ll;
ll res = 0;
int parent[N];
struct node{
int x, y, w;
}ege[N];
bool cmp(node a, node b){
return a.w < b.w;
}
void read(){
cin >> n >> k;
for(int i = 0; i < k; i ++ ) cin >> ege[i].x >> ege[i].y >> ege[i].w;
}
int find(int x){
if(parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
int kruskal(){
for(int i = 0; i < n; i ++ ) parent[i] = i;
sort(ege, ege + k, cmp);
for(int i = 0; i < k; i ++ ){
int px = find(ege[i].x), py = find(ege[i].y), w = ege[i].w;
if(px == py) res += w;
else parent[px] = py;
}
}
int main(){
read();
kruskal();
cout << res << endl;
return 0;
}