AcWing 859. Kruskal算法求最小生成树
原题链接
简单
作者:
C___
,
2021-12-05 21:21:25
,
所有人可见
,
阅读 134
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
const int N = 1e5 + 10;
struct node {
int a, b, c;
bool operator < (const node &_T) const {
return c < _T.c;
}
};
int n, m, f[N];
node e[N<<1];
int find(int x){
return x == f[x] ? x : f[x] = find(f[x]);
}
void Kruskal(){
// 将边权小的放在前面优先使用边权小的边建树
sort(e, e + m);
// res : 最小生成树边权总和 / cnt : 最小生成树边数
int res = 0, cnt = 0;
// 遍历所有边(优先使用的是边权小的边)
for(int i = 0; i < m; i++){
// x -> y 的边权是 w
int x = e[i].a, y = e[i].b, w = e[i].c;
int fx = find(x), fy = find(y);
// 不在同一个树中,但是要建立一个树,所以需要将两个树连接
if(fx != fy){
// 合并在一个树中
f[fy] = f[fx];
// 把边权加入最小生成树总边权重
res += w;
// 最小生成树中的边数 + 1
cnt++;
}
}
if(cnt == n - 1) printf("%d\n", res);
else printf("impossible\n");
}
int main(void){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) f[i] = i;
for(int i = 0; i < m; i++){
scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
}
Kruskal();
return 0;
}