怎样用堆优化最小生成树Prim？

附上代码C++
不要抽象的
最好比较通俗易懂
谢谢！

原理就是做个堆 保存所有未加入的点到当前强连通分量的距离 这样每次选取只需要O(1) 维护用O(logN) 比直接枚举选点的O(N)要快
代码（这个写的还可以 能当模板用）：
#include <cstdio>
#include <cstring>
#define INF 0xfff
#define typec Node
#define parent(i) ((i) / 2)
#define left(i) ((i) * 2)
#define right(i) ((i) * 2 + 1)

struct Node
{
int u, lowc;
Node(int su, int sl)
{
u = su; lowc = sl;
}
Node(){}
inline bool operator < (Node b) const
{
return lowc < b.lowc;
}
inline bool operator <= (Node b) const
{
return lowc <= b.lowc;
}
};

void swapc(typec &a, typec &b)
{
typec t = a;
a = b;
b = t;
}

void swim(typec heap[], int i)
{
if ( i < 2 )
return;

int p = parent(i);
if ( heap[i] < heap[p] )
{
swapc(heap[i], heap[p]);
}
swim(heap, p);
}

void sink(typec heap[], int i, int size)
{
int l = left(i);
if ( l > size )
return;

if ( l == size )
{
if ( heap[l] < heap[i] )
swapc(heap[l], heap[i]);
return;
}
int r = right(i);
int t = heap[l] < heap[r] ? l : r;
if ( heap[i] <= heap[t] )
return;

swapc(heap[i], heap[t]);
sink(heap, t, size);
}

void del(typec heap[], int i, int &size)
{
swapc(heap[i], heap[size]);
--size;
sink(heap, i, size);
}

int w[110][110], vis[110];
typec n[110];
int N;

int prim() // vertex: 0 ~ N-1
{
int i, res = 0;
memset(vis, 0, sizeof vis);

for ( i = 1; i < N; ++i ) // heap: 1 ~ size
{
n[i].lowc = w[0][i] ? w[0][i] : INF;
n[i].u = i;
}
for ( i = N / 2; i < N; ++i )
{
swim(n, i);
}
int size = N - 1, tw;
typec t;
while ( size )
{
t = n[1];
del(n, 1, size);
if ( vis[t.u] == 0 )
{
res += t.lowc;
vis[t.u] = 1;
for ( i = 1; i <= size; ++i )
{
tw = w[n[i].u][t.u];
if ( tw && tw < n[i].lowc )
{
n[i].lowc = tw;
swim(n, i);
}
}
}
}
return res;
}

int main()
{
int i, j, T;
scanf("%d", &T);
while ( T-- )
{
scanf("%d", &N);
for ( i = 0; i < N; ++i )
{
for ( j = 0; j < N; ++j )
scanf("%d", &w[i][j]);
}
printf("%d\n", prim() );
}
return 0;
}

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息