AcWing 859. Kruskal算法求最小生成树
原题链接
简单
作者:
跟着灿哥学切菜
,
2021-01-19 14:21:47
,
所有人可见
,
阅读 303
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 200010, INF = 0x3f3f3f3f;
int n, m;
int p[N];
struct Edge
{
int a, b, w;
//重载运算符
bool operator< (const Edge &W)const
{
return w < W.w;
}
}edges[M];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int kruskal()
{
//将所有边进行排序
sort(edges, edges + m);
for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集
//res中存储的是最小生成树中所有的边的权重之和。
//cnt表示此时一共最小生成树中有多少条边
int res = 0, cnt = 0;
//从小到大枚举所有边
for (int i = 0; i < m; i ++ )
{
//此时首先来通过边找到两个顶点, 以及相应的权重。
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
//找到a, b的祖宗节点
a = find(a), b = find(b);
//如果两个节点是不连通的, 此时将一个集合插入到另外的一个集合中
if (a != b)
{
p[a] = b;
res += w;
cnt ++ ;
}
}
//如果加的边数是小于n - 1的, 此时表示这个树是不连通的。
//此时因为有n个节点, 所以将这些点全部连接起来形成最小生成树, 需要n - 1条边
if (cnt < n - 1) return INF;
//输出所有边的权值之和
return res;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i ++ )
{
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
edges[i] = {a, b, w};
}
int t = kruskal();
if (t == INF) puts("impossible");
else printf("%d\n", t);
return 0;
}