AcWing 858. Prim算法求最小生成树
原题链接
简单
作者:
Sky_
,
2020-11-20 13:39:13
,
所有人可见
,
阅读 309
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxlen = 510;
const int INF = 0x3f3f3f3f;
int n, m;
int dist[maxlen];
int g[maxlen][maxlen];
bool st[maxlen];
int prim()
{
memset(dist, INF, sizeof(dist));
int res =0;
for(int i=0; i<n; i++) //迭代n次
{
int t = -1;
for(int j=1; j<=n; j++)
if(!st[j] && (t == -1 || dist[t] > dist[j])) //用t来扩展节点找到距离最近的节点
t = j;
if(i && dist[t]==INF) return INF; //不是第一次迭代(不是第一个点)而且最短距离为INF表示生成树不连通
if(i) res += dist[t]; //否则不是第一个点就将最短边加入结果
st[t] = true; //将当前扩展节点加到s中去
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, INF, sizeof(g));
while(m--)
{
int u,v,w;
cin>>u>>v>>w;
g[u][v] =g[v][u] = min(g[u][v], w); //无向图,而且存在重边取最小边
}
int t = prim();
if(t==INF) puts("impossible");
else cout<<t<<endl;
return 0;
}