AcWing 858. Prim算法求最小生成树
原题链接
简单
作者:
Hustle
,
2021-05-24 09:03:42
,
所有人可见
,
阅读 254
超级详细代码注释
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
// 最小生成树可看作一个集合
int n, m;
int g[N][N];
int dist[N]; // 此处距离为到集合中最短的距离 <即到集合中每个点的距离中的最短距离>
bool st[N]; // 标记该点是否被遍历过
int prim() {
memset(dist, 0x3f, sizeof dist); // 将每个点的距离给初始化为正无穷
int res = 0; // 存最小生成树的所有边长之和
for (int i = 0; i < n; ++ i) { // 迭代n次(将每个点都取一遍)
int t = -1; // 先将t初始化为-1
for (int j = 1; j <= n; ++ j) // 遍历所有点来寻找集合外的且距离集合最近的点 t
if (!st[j] && (t == -1 || dist[t] > dist[j]))
// 如果该点没有被遍历过 且(t没有被更新 或 t点到集合的距离 > 该点到集合的距离)
t = j;
// 则将该点更新为t点,<即找到了集合外的距离集合最近的点t(此处为j点)>
if (i && dist[t] == INF) return INF;
/* 如果i不为0(即不是第一个拿来迭代的点)
且 t点到集合的距离为正无穷(即t点与该集合的所有点没有边联通)*/
// 则返回无穷大,说明不存在最小生成树
if (i) res += dist[t];
// 如果i不为0(即不是第一个拿来迭代的点) 就更新 res (即将此时t点的距离加进来)
st[t] = true; // 将此时的t点给标记(被迭代过)
for (int j = 1; j <= n; ++ j)
dist[j] = min(dist[j], g[t][j]);
// 再用此时找到的t点去更新t点所有边的另一个点到集合的距离
/* 先更新res 再更新其余点的距离以防止负自环加入到集合中(最小生成树里不能有环的存在)*/
}
return res; //如果有最小生成树,则返回最后的边长总和
}
int main() {
cin >> n >> m;
memset(g, 0x3f, sizeof g); // 将所有边长也初始化为正无穷
while (m -- ) {
int a, b, c; // a, b 为该边的两个点, c为该边的权重(即边的长),<无向图>
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = min(g[a][b], c);
// 因为无向图且有重边,则储存双向边并更新为该两点的g[][]值与c(权重)的最小值
}
int ans = prim(); // 将最后答案存入ans中
if (ans == INF) puts("impossible") ; // 如果ans为INF(无穷大),则意味着无法形成最小生成树
else printf("%d\n", ans); // 反之,则输出生成的最小生成树的边长总和
return 0; // 结束快乐~
}