預流推進

in in if

預留推進

簡介

預流推進為網路流算法中的一種較為高效的一種算法，是最高標號法的基礎。可以想像在一個自來水管網的源頭儘可能多的注入水流之後，最多有多少水可以流到匯點去，由網路的各個節點和管道來約束流量。將每個節點都看成一個水站，他的通過能力是有限的不能通過的水只能退回去。

偽代碼如下:

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);
}
}
}