题目描述
算法思路:
将所有边按照权值的大小进行升序排序,然后从小到大一一判断。
如果这个边与之前选择的所有边不会组成回路,就选择这条边分;反之,舍去。
直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。
筛选出来的边和所有的顶点构成此连通网的最小生成树。
判断是否会产生回路的方法为:使用并查集。
在初始状态下给各个个顶点在不同的集合中。、
遍历过程的每条边,判断这两个顶点的是否在一个集合中。
如果边上的这两个顶点在一个集合中,说明两个顶点已经连通,这条边不要。如果不在一个集合中,则要这条边。
样例
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200010;
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()
{
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};
}
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;
// find 就是并查集的find函数
a = find(a), b = find(b);
if(a != b)
{
p[a] = b;
res += w;
cnt ++;
}
}
if(cnt < n - 1) puts("impossible");
else printf("%d\n", res);
return 0;
}