预留推进

简介

预流推进为网络流算法中的一种较为高效的一种算法，是最高标号法的基础。可以想象在一个自来水管网的源头尽可能多的注入水流之后，最多有多少水可以留到汇点去，由网络的各个节点和管道来约束流量。将每个节点都看成一个水站，他的通过能力是有限的不能通过的水只能退回去。

伪代码如下:

void maxflow(int s,int e)

{

初始化网络;

while(还有活跃的节点)

{

是否可以将流量推向下一节点；

不能推向下一节点，重新标记；

}

}

参考代码：

本代码来自互联网若有侵权，请联系此条创建人或者自行编辑

void push(int u,int v,int e)

{

int min=c[u]<g[u][v]? c[u]:g[u][v];

if (v==e) sum+=min;

g[u][v]-=min;

g[v][u]+=min;

c[u]-=min;

c[v]+=min;

}

void relabel(int u)

{

h[u]++;

}

void maxflow(int s,int e)

{

memset(c,0,sizeof(c));

c[s]=MAXINT;

c[e]=-MAXINT;

memset(h,0,sizeof(h));

h[s]=n;

sum=0;

queue<int> que; //活顶点队列

que.push(s);

while(!que.empty())

{

int u=que.front();

que.pop();

for (int i=0;i<n;i++)

if (u==s||h[u]==h[i]+1)

{

push(u,i,e);

if (i!=s&&i!=e) que.push(i);

}

if (u!=s&&u!=e&&c[u]>0)

{

relabel(u);

que.push(u);

}

}

}