堆优化版本的Prim

• prim和dijkstra每轮找最小边的松弛操作其实是同源的，因而受dijkstra堆优化的启发，那么prim也可以采用小根堆进行优化。
• 时间复杂度也由$O(n^2)$降为$O(nlogn)$。

测试一下吧：原题链接

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef int VertexType;
typedef int Info;
typedef pair<int,int> PII;const int N = 110;// 书面形式的邻接表
typedef struct ArcNode{int adjvex;Info weight;struct ArcNode* nextarc;
}ArcNode;
typedef struct VNode{VertexType data;        // 这里  结点编号就是结点表的下标  一一映射ArcNode* firstarc;
}VNode, AdjList[N];
typedef struct ALGraph{AdjList vertices;int vexnum, arcnum;ALGraph(){for(int i = 0;i < N;i ++)         vertices[i].firstarc = nullptr;}
}ALGraph;int prim_with_heap(ALGraph& G){int sum = 0;priority_queue<PII, vector<PII>, greater<PII>> heap;int dist[N];bool st[N];memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);dist[1] = 0;heap.push({0, 1});while(heap.size()){PII t = heap.top();heap.pop();int vex = t.second, distance = t.first;if(st[vex])     continue;st[vex] = true;sum += distance;for(ArcNode* parc = G.vertices[vex].firstarc;parc;parc = parc -> nextarc)if((parc -> weight) < dist[parc -> adjvex]){dist[parc -> adjvex] = parc -> weight;heap.push({parc -> weight, parc -> adjvex});}}return sum;
}void add(ALGraph& G, VertexType a, VertexType b, Info w){   // a -> bVNode* u = &G.vertices[a];ArcNode* newarc = new ArcNode;newarc -> adjvex = b;newarc -> weight = w;newarc -> nextarc = u -> firstarc;u -> firstarc = newarc;     // 头插法G.arcnum ++;
}int main(){ALGraph g;cin >> g.vexnum;for(int i = 1;i <= g.vexnum;i ++)for(int j = 1;j <= g.vexnum;j ++){int w;cin >> w;add(g, i, j, w);}int sum = prim_with_heap(g);cout << sum << endl;return 0;
}