最大流——HLPP算法

名字长,跑得快：最高标号预流推进算法!

最高标号预流推进算法High Level Preflow Push是最大流里最快的算法。我是偶然在网上看到这个算法的，其时间复杂度达到了令人发指的O(|E|²*sqrt(|V|))（Dinic，SAP，ISAP都是O(|E|²*|V|)！）。但是查了半天资料，发现关于这个算法的讲解十分少。经过一周多的钻研，终于差不多搞懂了:)。

非常感谢石姐的鼎力相助！

---

目录

算法思想算法步骤代码

---

算法思想

预流推进算法将每个点看做一个可以存储流的“水池”，其中存有流的点称为活动节点;对于每个非s或t的点，流入该点的流只可能有两个去向：流入汇点t，流回源点s;预流推进算法从源点开始沿边向其它点推流，之后每次选一个活动节点通过推流，试图使其变得不活动。当所有节点都是不活动节点时，算法就结束了;以上是传统预流推进算法的主要思想。而最高标号预流推进算法就是先预处理了一个距离标号h，通过堆或优先队列，没次选出h最大的点进行推流，以减少重复操作，降低了复杂度。

---

算法步骤

通过bfs预处理出距离标号h，即到达汇点t的最短距离;将从源点s出发的边设为满流，到达的点v标记为活动节点并加入到优先队列中;从优先队列中不断取出点u进行推流操作，要求到达点v的必须满足h(u)==h(v)+1;若推流后u中仍有余流，则进行重标号。将h(u)设为min{h(v)}，再次加入优先队列并重复步骤3;当优先队列为空时，结束算法。

---

代码

#include <cstdio> #include <queue> #include <cstring> using namespace std; #define min(a,b) (a<b ? a:b) const int MAXN=305,MAXM=100005,INF=~0U>>1; int cnt,head[MAXN]; bool vis[MAXN]; struct line{ int to,next,cap; line(){ next=-1; } }edge[MAXM]; struct data{ int x,h,ef; friend bool operator< (const data &a,const data &b){ return a.h<b.h; } }node[MAXN]; priority_queue<data> q; queue<int> tmpq; inline void add(int u,int v,int w){ edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; edge[cnt].cap=w; ++cnt; } void bfs(int t){ tmpq.push(t); vis[t]=true; int u,v; while(tmpq.size()){ u=tmpq.front(); for(int i=head[u];i!=-1;i=edge[i].next){ v=edge[i].to; if(!vis[v]){ node[v].h=node[u].h+1; tmpq.push(v); vis[v]=true; } } tmpq.pop(); } } int hlpp(int n,int s,int t){ for(int i=1;i<=n;++i) node[i].x=i; bfs(); data tmp; int u,v,f,tmph; for(int i=head[s];i!=-1;i=edge[i].next){ v=edge[i].to; edge[i^1].cap+=edge[i].cap; node[v].ef+=edge[i].cap; edge[i].cap=0; q.push(node[v]); } node[s].h=n; while(q.size()){ tmp=q.top(); q.pop(); u=tmp.x; tmph=INF; for(int i=head[u];i!=-1 && node[u].ef;i=edge[i].next){ v=edge[i].to; if(edge[i].cap){ if(node[u].h==node[v].h+1){ if(v!=s && v!=t && node[v].ef==0) q.push(node[v]); f=min(edge[i].cap,node[u].ef); edge[i].cap-=f; edge[i^1].cap+=f; node[u].ef-=f; node[v].ef+=f; } else tmph=min(tmph,node[v].h); } if(node[u].ef){ node[u].h=tmph+1; q.push(node[u]); } } return node[t].ef; } int main(){ memset(head,-1,sizeof(head)); int n,m,s,t,tmpu,tmpv,tmpw; scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=m;++i){ scanf("%d%d%d",&tmpu,&tmpv,&tmpw); add(tmpu,tmpv,tmpw); add(tmpv,tmpu,tmpw); } printf("%d",hlpp(n,s,t)); return 0; }

---

ps：第一次写博客，如果有什么不足，还请大家指出来，谢谢！:)