AcWing 858. Prim算法求最小生成树
原题链接
简单
作者:
芝居気
,
2021-12-05 19:27:36
,
所有人可见
,
阅读 137
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
const int N = 1005;
unordered_map<int, unordered_map<int, int>> g;
int dis[N];
int n, m;
bool st[N];
int prim()
{
memset(dis, 0x3f, sizeof dis);
int res = 0;
for (int i = 0; i < n; i++)
{
int t = -1;
for (int j = 1; j <= n; j++)
{
if (!st[j] && (t == -1 || dis[t] > dis[j]))//找到所有未确定的点离集合最小的点。
t = j;
}
if (i && dis[t] == 0x3f3f3f3f) return 0x3f3f3f3f;//如果该点都不联通,这无法生成
if (i) res += dis[t];//加上联通值
for (auto j : g[t])
{
dis[j.first] = min(dis[j.first], g[t][j.first]);
}
//for (int j = 1; j <= n; j++) dis[j] = min(dis[j], g[t][j]);//扩展松弛操作
st[t] = 1;
}
return res;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
g[i][i] = 0;
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c);
}
int t;
if ((t=prim()) == 0x3f3f3f3f) cout << "imposible" << endl;
else cout << t;
}