在 Prim 演算法中使用 pb_ds 堆優化
Prim 演算法用于求最小生成樹（Minimum Spanning Tree，簡稱 MST），其本質是一種貪心的加點法，對于一個各點相互連通的無向圖而言，Prim 演算法的具體步驟如下：
令 \(G=(V,E)\) 表示原圖，\(G'=(V',E')\) 表示 \(G\) 的最小生成樹，\(dis_u\) 表示節點 \(u\) 到任意 \(v \in V'\) 的最小距離（初始化為 \(+\infty\)），
- 任取節點\(s \in V\)，令 \(dis_s=0\)；
- 找到一個節點 \(u \in \complement_V V'\)，使得 \(dis_u\) 最小；
- 將 \(u\) 加入 \(V'\)，\(dis_u\) 所代表的邊加入 \(E'\)；
- 對于任意邊 \((u,v)\in \complement_E E'\)，令 \(dis_v=\min \{dis_v,w\}\)，其中 \(w\) 為邊 \((u,v)\) 的權值；
- 重復程序 2 到 程序 4，直到 \(V'=V\)，
該演算法的正確性證明可以參考 OI Wiki，
樸素的 Prim 演算法時間復雜度為 \(O(n^2+m)\)，其中大部分時間都消耗在操作 2 上，可以考慮利用堆對其進行優化，用二叉堆等不支持 \(O(1)\) decrease-key 操作的堆優化后時間復雜度為 \(O((n+m)\log n)\)，用 Fibonacci 堆優化后的時間復雜度為 \(O(n \log n+m)\)（參考 OI Wiki），相較于 Kruskal 演算法，Prim 演算法在稠密圖上的效率更高，
Prim 演算法中大量使用到 decrease-key 操作，在 OI 競賽中，為節約時間，可以使用 C++ 標準庫中封裝好的資料結構代替手寫堆，由于 std::priority_queue 不支持 decrease-key 操作，常常用 std::map 代替，實際上，std::set 內部實作是一棵常數較大的紅黑樹，這種用法顯然會影響運行效率，鑒于當前 OI 競賽中幾乎全部采用 GNU 編譯器，且 CCF 已經明確允許使用 pb_ds，我們可以使用 __gnu_pbds::priority_queue 作為堆來優化 Prim 演算法，可以選擇不同種類的堆作為內部實作，其中最快也是默認的是 配對堆（Pairing Heap），具體使用方式見代碼模板（P3366 【模板】最小生成樹 - 洛谷，需要 C++14 標準）：
#include <bits/extc++.h>
using namespace std;
const int maxn = 5005;
const int inf = 0x3f3f3f3f;
int n, m;
vector<pair<int, int>> g[maxn];
__gnu_pbds::priority_queue<pair<int, int>, greater<>> heap;
__gnu_pbds::priority_queue<pair<int, int>, greater<>>::point_iterator p[maxn]; // dis[i] and iterator for decrease-key
int prim() {
int ans = 0;
p[1] = heap.push(make_pair(0, 1));
for (int i = 2; i <= n; ++i)
p[i] = heap.push(make_pair(inf, i));
while (!heap.empty()) {
if (heap.top().first == inf)
return -1;
int u = heap.top().second;
ans += heap.top().first;
heap.pop();
p[u] = heap.end();
for (auto& i : g[u])
if (p[i.first] != heap.end() && i.second < p[i.first]->first)
heap.modify(p[i.first], make_pair(i.second, i.first));
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v, w;
cin >> u >> v >> w;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
int ans = prim();
if (ans != -1)
cout << ans << endl;
else
cout << "orz" << endl;
return 0;
}
轉載請注明出處，原文地址：https://www.cnblogs.com/na-sr/p/prim-pbds.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/421639.html
標籤：其他