C++
$\color{#cc33ff}{— > 算法基础课题解}$
kruskal 算法:
1、将所有边按权重大小从小到大排序
2、(从小到大)枚举每条边a, b
- 如果这条边(a, b)不连通
将这条边加入到集合中去
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
int n, m;
int p[N];
struct Edge { // 结构体存储所有边
int a, b, w;
bool operator < (const Edge &W) const { // 重载小于号
return w < W.w;
}
}edges[N];
int find(int x) { // 并查集
if (p[x] != x) p[x] =find(p[x]);
return p[x];
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i ++) {
int a, b, w;
cin >> a >> b >> w;
edges[i] = {a, b, w};
}
//kruskal 算法
sort(edges, edges + m); // 把所有边排序
for (int i = 1; i <= n; i ++) p[i] = i; // 初始化并查集
int res = 0, cnt = 0; // res : 最小生成树中所有树边的权重之和 cnt : 当前加入了多少条边
for (int i = 0; i < m; i ++) { // 从小到大枚举所有边
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if (a != b) {
p[a] = b; // 合并集合
res += w;
cnt ++;
}
}
if (cnt < n - 1) cout << "impossible";
else cout << res;
return 0;
}
tql