关于配对堆的一些小姿势:
1, 配对堆是一颗多叉树.
2, 包含优先队列的所有功能, 可用于优化 Dijkstra 算法.
3, 属于可并堆, 因此对于集合合并维护最值的问题很实用.
4, 速度快于一般的堆结构 (左偏树, 斜堆, 随机堆......), 具体时间复杂度:
合并 (Merge):$O(1)$;
插入 (Insert/Push):$O(1)$;
修改值 (Change):$O(1) \sim O(\log n)$;
取出维护的最值 (Top):$O(1)$;
弹出堆顶元素 (Pop):$O(\log n)$;
我们依然拿洛谷的 P4779 [模板] 单源最短路径 (标准版) https://www.luogu.org/problemnew/show/P4779 来验证代码的正确性.
以下是配对堆优化 Dijkstra 算法的 AC 代码:
- #include<bits/stdc++.h>
- #include<ext/pb_ds/priority_queue.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- typedef pair<int,int> pii;
- typedef __gnu_pbds::priority_queue<pii,greater<pii>,pairing_heap_tag> Heap;
- const int maxn=1e5+10;
- const int INF=0x3f3f3f3f;
- int n,m,s;
- struct Edge{
- int u,v,w;
- Edge(int _u=0,int _v=0,int _w=0){u=_u,v=_v,w=_w;}
- };
- vector<Edge> E;
- vector<int> G[maxn];
- void addedge(int u,int v,int w)
- {
- E.push_back(Edge(u,v,w));
- G[u].push_back(E.size()-1);
- }
- int d[maxn];
- void dijkstra()
- {
- memset(d,0x3f,sizeof(d));
- Heap Q;
- Heap::point_iterator id[maxn];
- d[s]=0;
- id[s]=Q.push(make_pair(d[s],s));
- while(!Q.empty())
- {
- int u=Q.top().second; Q.pop();
- for(int i=0;i<G[u].size();i++)
- {
- Edge &e=E[G[u][i]]; int v=e.v;
- if(d[v]>d[u]+e.w)
- {
- d[v]=d[u]+e.w;
- if(id[v]!=0) Q.modify(id[v],make_pair(d[v],v));
- else id[v]=Q.push(make_pair(d[v],v));
- }
- }
- }
- }
- int main()
- {
- scanf("%d%d%d",&n,&m,&s);
- for(int i=1;i<=m;i++)
- {
- int u,v,w;
- scanf("%d%d%d",&u,&v,&w);
- addedge(u,v,w);
- }
- dijkstra();
- for(int i=1;i<=n;i++) printf("%d%s",d[i],((i==n)?"\n":" "));
- }
来源: http://www.bubuko.com/infodetail-2854851.html