AcWing 3210. 最优灌溉
原题链接
简单
作者:
RainSure
,
2022-02-15 23:09:08
,
所有人可见
,
阅读 182
最小生成树模板题
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1010, M = 100010;
typedef struct node
{
int a, b, c;
bool operator < (const struct node w) const{
return c < w.c;
}
}Node;
Node edges[M];
int p[maxn];
int find(int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
int n, m;
int kruskal()
{
sort(edges, edges + m);
for(int i = 1; i <= n; i ++) p[i] = i;
int res = 0;
int num = 0;
for(int i = 0; i < m; i ++){
int a = edges[i].a, b = edges[i].b;
int fa = find(a), fb = find(b);
if(fa != fb){
num ++;
res += edges[i].c;
p[fa] = fb;
}
}
return res;
}
int main()
{
cin >> n >> m;
for(int i = 0; i < m; i ++){
cin >> edges[i].a >> edges[i].b >> edges[i].c;
}
int x = kruskal();
cout << x << endl;
return 0;
}