AcWing 858. Prim算法求最小生成树
原题链接
简单
作者:
风起于浮萍之末
,
2024-01-28 10:10:19
,
所有人可见
,
阅读 36
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=510,INF = 0x3f3f3f3f;
int n,m;
int dist[N];// 距离数组
int g[N][N];
bool st[N];
int prim(){
int res=0;
memset(dist,0x3f,sizeof dist);//初始化
for(int i=0;i<n;i++){ //一开始没有点加入
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j]&&(t==-1||dist[t]>dist[j])){//st[j] 表示在集合外 t==-1 表示还没有找到
t=j;//最短距离的点
}
}
if(i&&dist[t]==INF) return INF;// 距离最近的点 到我们这个集合距离式正无穷
if(i) res+=dist[t];// 第一个点没有边
st[t]=true;
// 用某个点 更新到集合内部的距离
for(int j=1;j<=n;j++){
dist[j]=min(dist[j],g[t][j]);//更新到集合的距离 用距离最小的当
}
}
return res;
}
int main(){
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = min(g[a][b], c); // 注意是无向图
}
int t = prim();
if (t == INF) puts("impossible");
else printf("%d\n", t);
return 0;
}