預流推進

預流推進為網路流算法中的一種較為高效的一種算法，是最高標號法的基礎。

基本介紹

• 中文名：預流推進
• 性質：網路流算法
• 意義：最高標號法的基礎
• 套用領域：計算機

預留推進

簡介

可以想像在一個自來水管網的源頭儘可能多的注入水流之後，最多有多少水可以流到匯點去，由網路的各個節點和管道來約束流量。將每個節點都看成一個水站，他的通過能力使有限的不能通過的水只能退回去。

偽代碼如下:

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

}

}

}