AcWing 858. Prim算法求最小生成树[链式前向星]
原题链接
简单
作者:
Kylin
,
2019-10-02 00:29:25
,
阅读 547
#include<bits/stdc++.h>
using namespace std;
const int maxm = 200005;
const int inf = 0x3f3f3f3f;
struct edge{
int v, w, next;
}e[maxm << 1];
int cnt, n, m, sum, t, p, now = 1;
int dis[5005], head[maxm], vis[5005];
int a, b, c;
void add(int uu, int vv, int ww)
{
e[++cnt].v = vv;
e[cnt].w = ww;
e[cnt].next = head[uu];
head[uu] = cnt;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
cin >> a >> b >> c;
add(a, b, c); add(b, a, c); // 无向图,所以两个点之间连上
}
for(int i = 1; i <= n; i++)
dis[i] = inf;
for(int i = head[1]; i; i = e[i].next) // 判断重边
dis[e[i].v] = min(e[i].w, dis[e[i].v]);
while(++t < n)
{
vis[now] = 1;
int minn = inf;
now = -1;
for(int i = 1; i <= n; i++)
{
if(!vis[i] && minn > dis[i])
{
minn = dis[i];
now = i;
}
}
if(now == -1) // 若有一个点更新完后dis[]数组仍为 inf,那么不能构成最小生成树
{
cout << "impossible";
return 0;
}
sum += minn;
for(int i = head[now]; i; i = e[i].next) //更新dis[]数组
{
if(!vis[e[i].v] && e[i].w < dis[e[i].v])
dis[e[i].v] = e[i].w;
}
}
cout << sum;
return 0;
}