壓入與重標記算法

與Ford-Fulkerson方法不同，壓入和重標記算法不是檢查整個殘留網絡來找出增廣路徑，而是每次僅對一個頂點進行操作，並且僅檢查殘留網絡中該頂點的相鄰頂點。壓入和重標記算法引入了一個新的概念叫做餘流，餘流的定義為e(u)=f(V,u)。我們知道，在流網絡滿足三個限制條件的情況下有e(u)=0，但是在該算法的執行過程中，並不能保證流守恆，但是卻保持了一個“前置流”，前置流滿足反對稱性、容量限制、和放寬條件的流守恆特性，而這個放寬條件的流守恆特性就是指e(u)>=0，當e(u)>0時，則稱頂點u溢出。下面對壓入和重標記算法給出一個更直觀的理解。

繼續把流網絡中的邊看成是運輸的管道，與之前Ford-Fulkerson思想有所不同的是，這裏我們將每個頂點看成是一個水庫，此時，上面所講的餘流實際上就是某一個水庫中的蓄水量。為了算出最終的最大流，我們是不允許水庫中有餘流的，所以就要將存在餘流的水庫中的水向其他能聚集液體的任意大水庫排放，這個操作就是壓入操作。而壓入的方式則取決於頂點的高度，頂點的高度是一個比較抽象的概念，我們可以認為當餘流從水庫u壓入其他水庫及以後的過程中，水庫u的高度隨之增加，我們僅僅把流往下壓，即從較高頂點壓入向較低頂點壓，這樣就不會出現剛把一個流從u壓入v後馬上又被往回壓的死循環的情況了。源點的高度固定為|V|，匯點的高度固定為0，所有其他頂點的高度開始時都是0，並逐步增加。算法首先從源點輸送儘可能多的流出去，也就是恰好填滿從源點出發每條管道，當流進入一箇中間頂點時，它就聚集在該頂點的水庫中，並且最終將從這裏繼續向下壓入。

在壓入的過程中可能會發生下列情況，離開頂點u且未被填滿的管道所連接的頂點的高度與u相等或者高於u，根據我們的壓入規則，這時候是沒有辦法繼續往下壓入的。為了使溢出頂點u擺脱其餘流，就必須增加它的高度，即稱為重標記操作。我們把u的高度增加到比其最低的相鄰頂點（未被填滿的管道所連接的頂點）的高度高一個單位。顯然，當一個頂點被重標記後，至少存在着一條管道可以排除更多的流。

最終，有可能到達匯點的所有流均到達匯點，為了使前置流稱為合法的流，根據算法的執行過程，算法會繼續講頂點的高度標記高於源點的固定高度|V|，以便把所有頂點中的餘流送回源點。當除去源點和匯點的所有水庫的水均為空時，我們就得到了最大流了。

（真正能想讀懂的朋友最好還是要參閲《算法導論》）

（應該沒問題，用過好幾次了）：

#include

using namespace std;

ifstream cin("");

ofstream cout("netflow.out");

const int Max=1001;

int edges[Max][Max],f[Max][Max],c[Max][Max],e[Max],h[Max],vertices;

bool visited[Max]={false};i

nt push_relable(int s,int t)

{

//Initializeint queue[10*Max],head=0,tail=0;//隊列可以用循環隊列

queue[0]=s;

visited[s]=true;

for(int i=1;i<=edges[s][0];i++)

{

int u=edges[s][i];

f[s][u]=c[s][u];

f[u][s]=-c[s][u];

e[s]-=c[s][u];

e[u]=c[s][u];

visited[u]=true;

queue[++tail]=u;

}h[s]=vertices;

for(;head<=tail;head++){

int u=queue[head];

visited[u]=false;

//push

for(int i=1;i<=edges[u][0];i++)

{

int v=edges[u][i];

int resi=c[u][v]-f[u][v];

if(resi>0&&h[u]==h[v]+1)

{

int Min=min(resi,e[u]);

f[u][v]+=Min;

f[v][u]=-f[u][v];

e[u]-=Min;

e[v]+=Min;

if(v!=s&&v!=t&&!visited[v])

{

visited[v]=true;

queue[++tail]=v;

}

}

} //relable

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

{

visited[u]=true;

queue[++tail]=u;

int Min=(1<<30);

for(int i=1;i<=edges[u][0];i++)

{

int v=edges[u][i];int resi=c[u][v]-f[u][v];

if(resi>0&&h[v]

}

h[u]=max(h[u],Min+1);

}

}

//compute netflow

int flow=0;

for(int i=1;i<=edges[s][0];i++) flow+=f[s][edges[s][i]];

return flow;}

int main(){

cin>>vertices;int P;cin>>P;for(int i=1;i<=P;i++){

int a,b; cin>>a>>b;//必須記錄反向邊：正向邊和反向邊都有可能在殘留。

edges[a][++edges[a][0]]=b; edges[b][++edges[b][0]]=a; c[a][b]=1; c[b][a]=0;

}cout<

（百度什麼破編輯器，再不能寫代碼，百科別想辦了，另外數學公式趕快弄好！）