【模板】prim的heap优化

简单的代码。。

时间复杂度为O((n + m)logn)

大部分情况下还是跑不过kruskal的，慎用。

1 #include <cstdio> 2 #include <queue> 3 #include <cstring> 4 #define heap pair<int, int> 5 6 using namespace std; 7 8 int n, m, cnt, ans; 9 int head[5001], to[001], next[001], val[001]; 10 bool vis[5001]; 11 priority_queue <heap, vector <heap>, greater <heap> > q; 12 13 inline void add(int x, int y, int z) 14 20 21 inline void queue_prim() 22 40 } 41 } 42 43 int main() 44 54 queue_prim(); 55 printf("%d", ans); 56 return 0; 57 }
View Code

上一篇：[NOI2003]Editor（块状链表）

下一篇：[luoguP1866]滑动窗口（单调队列）

---

stl 模板 堆 最小生成树 prim