#include<bits/stdc++.h>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N]; //储存边
int dist[N]; //储存点到集合的距离
int st[N]; //判断点是否已经加入集合
int Prim() {
int res = 0;
for (int i = 0; i < n; i++) { //n个节点遍历n次
int t = -1;
for (int j = 1; j <= n; j++){
if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; //某个节点没有被加入集合 并且是未被加入集合中的距离离集合最小的
}
if (i && dist[t] == INF) return INF; // 如果某个点距离集合距离为INF就不能生成最小生成树
if (i) res += dist[t]; // 加入一条边到集合中就加上他的权重
for (int j = 1; j <= n; j++) { //
if (!st[j]) dist[j] = min(dist[j], g[t][j]); //用这个点更新其他点的距离
}
st[t] = true;
}
return res;
}
int main() {
cin >> n >> m;
memset(dist, 0x3f, sizeof dist);
memset(g, 0x3f, sizeof g);
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
g[a][b] = g[b][a] = min(g[a][b], w);
}
int t = Prim();
if (t == INF) puts("impossible");
else cout << t;
return 0;
}
标签:Prim,int,858,最小,算法,集合,dist,INF
From: https://www.cnblogs.com/echoT/p/16823464.html