AcWing 858. Prim算法求最小生成树
原题链接
简单
作者:
369pro
,
2024-03-25 16:51:15
,
所有人可见
,
阅读 4
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N = 505;
struct edge{
int v, w;
};
int cost = 0;
vector<edge> e[N];
// d[i]表示节点i到生成树的最短距离
int d[N], vis[N];
bool prim(int s, int n){
d[s] = 0;
// 生成树并入的节点个数
int cnt = 0;
for(int i = 1; i <= n; i++){
// 哨兵节点
int u = 0;
for(int j = 1; j <= n; j++){
if(!vis[j] && d[j] < d[u]) u = j;
}
vis[u] = 1;
// 并入树的时候再加权值
cost += d[u];
// 存在节点u到树的路径
if(d[u] != 0x3f3f3f3f) cnt++;
for(auto edge : e[u]){
int v = edge.v, w = edge.w;
if(d[v] > w) {
d[v] = w;
// cost += w;
}
}
}
return cnt == n;
}
int main(){
int n, m;
cin >> n >> m;
while(m--){
int u, v, w;
cin >> u >> v >> w;
e[u].push_back({v, w});
e[v].push_back({u, w});
}
memset(d, 0x3f, sizeof(d));
bool flag = prim(1, n);
if(flag) cout << cost;
else cout << "impossible";
}