题目描述
堆优化方法的prim算法解决此问题。
最终发现运行时间还是会略高于kruskal算法。虽然两种方法时间复杂度都为 o(m log m)。
分析一下差异原因:堆优化方法是将每条边依次插入堆中,最坏情况下插入m条边,然后进行堆排序。
kruskal算法是将数组内的m条边一次快速排序完,不用进行插入过程。
样例
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010, M = 400010;
typedef pair<int,int> PII;
int d[N];
int h[N], ne[M], e[M], w[M], idex;
bool st[N];
int res;
void add(int x, int y, int z)
{
e[++idex] = y;
ne[idex] = h[x];
w[idex] = z;
h[x] = idex;
}
int main()
{
int n, m;
cin >> n >> m;
memset(d, 0x3f, sizeof d);
memset(w, 0x3f, sizeof w);
priority_queue<PII, vector<PII>, greater<PII>> q;
while(m --)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
d[1] = 0;
q.push({0,1});
while(q.size())
{
PII a = q.top();
q.pop();
int dist = a.first;
int t = a.second;
if (st[t]) continue;
st[t] = true;
res += dist;
for(int i = h[t]; i != 0; i = ne[i])
{
int j = e[i];
if(!st[j] && d[j] > w[i])
{
d[j] = w[i];
q.push({d[j],j});
}
}
}
for(int i = 1; i <= n; i ++)
if(!st[i])
{
printf("impossible\n");
return 0;
}
printf("%d\n",res);
return 0;
}