相關定義
前向弧和後向弧在網路D(V,A)中,如果對連線發點vs和收點vt的一條鏈P,方向規定為從vs到vt,則當鏈P中弧(vi,vj)的方向與規定的方向一致時,稱弧(vi,vj)為前向弧,否則稱為後向弧。不在這條鏈上的弧,不定義前向弧和後向弧。
可擴充鏈
設{fij}為一可行流(假設為非負值),如果存在從發點vs到收點vt的鏈P,在鏈P上,下列兩條同時滿足,則稱P為可擴充鏈:①對於P上的前向弧(vi,vj)有fij<cij。
②對於P上的後向弧(vi,vj)有fij>0。[1]可擴充鏈P的費用
設對於可行流f存在可擴充鏈P,當以ε=1調整f而得到可行流f'時,兩流的費用之差成為可擴充鏈p的費用。其中P+和P-分別表示p上的前向弧和後向弧。
解決方法
解決最小費用最大流問題，一般有兩條途徑。一條途徑是先用最大流算法算出最大流，然後根據邊費用，檢查是否有可能在流量平衡的前提下通過調整邊流量，使總費用得以減少？只要有這個可能，就進行這樣的調整。調整後，得到一個新的最大流。然後，在這個新流的基礎上繼續檢查，調整。這樣疊代下去，直至無調整可能，便得到最小費用最大流。這一思路的特點是保持問題的可行性（始終保持最大流），向最優推進。另一條解決途徑和前面介紹的最大流算法思路相類似，一般首先給出零流作為初始流。這個流的費用為零，當然是最小費用的。然後尋找一條源點至匯點的增流鏈，但要求這條增流鏈必須是所有增流鏈中費用最小的一條。如果能找出增流鏈，則在增流鏈上增流，得出新流。將這個流做為初始流看待，繼續尋找增流鏈增流。這樣疊代下去，直至找不出增流鏈，這時的流即為最小費用最大流。這一算法思路的特點是保持解的最優性（每次得到的新流都是費用最小的流），而逐漸向可行解靠近（直至最大流時才是一個可行解）。
由於第二種算法和已介紹的最大流算法接近，且算法中尋找最小費用增流鏈，可以轉化為一個尋求源點至匯點的最短路徑問題，所以這裡介紹這一算法。
在這一算法中，為了尋求最小費用的增流鏈，對每一當前流，需建立伴隨這一網路流的增流網路。例如圖1網路G是具有最小費用的流，邊旁參數為c(e),f(e),w(e)，而圖2即為該網路流的增流網路G′。增流網路的頂點和原網路相同。按以下原則建立增流網路的邊：若G中邊(u，v)流量未飽，即f(u,v)<e(u,v)，則G'中建邊(u,v)，賦權w'(u,v)=w(u,v)；若G中邊(u,v)已有流量，即f(u,v)〉0，則G′中建邊(v,u)，賦權w′(v,u)=-w(u,v)。建立增流網路後，即可在此網路上求源點至匯點的最短路徑，以此決定增流路徑，然後在原網路上循此路徑增流。這裡，運用的仍然是最大流算法的增流原理，唯必須選定最小費用的增流鏈增流。
計算中有一個問題需要解決。這就是增流網路G′中有負權邊，因而不能直接套用標號法來尋找X至y的最短路徑，採用其它計算有負權邊的網路最短路徑的方法來尋找x至y的最短路徑，將大大降低計算效率。為了仍然採用標號法計算最短路徑，在每次建立增流網路求得最短路徑後,可將網路G的權w(e)做一次修正，使再建的增流網路不會出現負權邊，並保證最短路徑不至於因此而改變。下面介紹這種修改方法。當流值為零，第一次建增流網路求最短路徑時，因無負權邊，當然可以採用標號法進行計算。為了使以後建立增流網路時不出現負權邊，採取的辦法是將G中有流邊（f(e)>0）的權w(e)修正為0。為此，每次在增流網路上求得最短路徑後，以下式計算G中新的邊權w"(u,v)：
w"(u,v)=L(u)-L(v)+w(u,v)(*)
式中L(u),L(v)--計算G′的x至y最短路徑時u和v的標號值。第一次求最短徑時如果(u,v)是增流路徑上的邊，則據最短路徑算法一定有L(v)=L(u)+w'(u,v)=L(u)+w(u,v)，代入(*)式必有w″(u,v)=0。如果(u,v)不是增流路徑上的邊，則一定有：L(v)≤L(u)+w(u,v)，代入(*)式則有w(u,v)≥0。
可見第一次修正w(e)後，對任一邊，皆有w(e)≥0，且有流的邊（增流鏈上的邊），一定有w(e)=0。以後每次疊代計算，若f(u,v)>0，增流網路需建立(v,u)邊，邊權數w'(v,u)=-w(u,v)=0，即不會再出現負權邊。此外，每次疊代計算用(*)式修正一切w(e)，不難證明對每一條x至y的路徑而言，其路徑長度都同樣增加L(x)-L(y)。因此，x至y的最短路徑不會因對w(e)的修正而發生變化。
【計算步驟】
1.對網路G=[V,E,C,W]，給出流值為零的初始流。2.作伴隨這個流的增流網路G′=[V′,E′,W′]。G′的頂點同G：V′=V。若G中f(u,v)<c(u,v)，則G′中建邊(u,v)，w(u,v)=w(u,v)。若G中f(u,v)>0，則G′中建邊(v,u)，w′(v,u)=-w(u,v)。
3.若G′不存在x至y的路徑，則G的流即為最小費用最大流，停止計算；否則用標號法找出x至y的最短路徑P。
4.根據P，在G上增流：對P的每條邊(u,v)，若G存在(u,v)，則(u,v)增流；若G存在(v,u)，則(v,u)減流。增（減）流後，應保證對任一邊有c(e)≥f(e)≥0。
5.根據計算最短路徑時的各頂點的標號值L(v)，按下式修改G一切邊的權數w(e):L(u)-L(v)+w(e)→w(e)。
6.將新流視為初始流，轉2。
算法舉例
augmentpath直譯為“增廣路”，其思想大致如下：
原有網路為G，設有一輔助圖G'，其定義為V(G')=V(G)，E(G')初始值（也就是容量）與E(G)相同。每次操作時從Source點搜尋出一條到Sink點的路徑，然後將該路徑上所有的容量減去該路徑上容量的最小值，然後對路徑上每一條邊<u,v>添加或擴大反方向的容量，大小就是剛才減去的容量。一直到沒有路為止。此時輔助圖上的正向流就是最大流。
我們很容易覺得這個算法會陷入死循環，但事實上不是這樣的。我們只需要注意到每次網路中由Source到Sink的流都增加了，若容量都是整數，則這個算法必然會結束。
尋找通路的時候可以用DFS，BFS最短路等算法。就這兩者來說,BFS要比DFS快得多，但是編碼量也會相應上增加。增廣路方法可以解決最大流問題，然而它有一個不可避免的缺陷，就是在極端情況下每次只能將流擴大1（假設容量、流為整數），這樣會造成性能上的很大問題，解決這個問題有一個複雜得多的算法，就是預推進算法。
pushlabel直譯為“預推進”算法。
Push-relabel
直譯為壓入與重標記算法
除了用各種方法在剩餘網路中不斷找增廣路(augmenting)的Ford-Fulkerson系的算法外，還有一種求最大流的算法被稱為壓入與重標記(Push-Relabel)算法。它的基本操作有：壓入，作用於一條邊，將邊的始點的預流儘可能多的壓向終點；重標記，作用於一個點，將它的高度（也就是label）設為所有鄰接點的高度的最小值加一。Push-Relabel系的算法普遍要比Ford-Fulkerson系的算法快，但是缺點是相對難以理解。
Relabel-to-Front使用一個鍊表保存溢出頂點，用Discharge操作不斷使溢出頂點不再溢出。
Discharge的操作過程是：若找不到可被壓入的臨邊，則重標記，否則對臨邊壓入，直至點不再溢出。
算法的主過程是：首先將源點出發的所有邊充滿，然後將除源和匯外的所有頂點保存在一個鍊表里，從鍊表頭開始進行Discharge，如果完成後頂點的高度有所增加，則將這個頂點置於鍊表的頭部，對下一個頂點開始Discharge。
Relabel-to-Front算法的時間複雜度是O(V^3)，還有一個叫HighestLabelPreflowPush的算法複雜度據說是O(V^2*E^0.5)。我研究了一下HLPP，感覺它和Relabel-to-Front本質上沒有區別，因為Relabel-to-Front每次前移的都是高度最高的頂點，所以也相當於每次選擇最高的標號進行更新。還有一個感覺也會很好實現的算法是使用佇列維護溢出頂點，每次對pop出來的頂點discharge，出現了新的溢出頂點時入隊。Push-Relabel類的算法有一個名為gapheuristic的最佳化，就是當存在一個整數0<k<V，沒有任何頂點滿足h[v]=k時，對所有h[v]>k的頂點v做更新，若它小於V+1就置為V+1。
c++程式舉例
#include<cstdio>constlongmaxn=1000+10;
constlongmaxm=440000+100;
constlongmaxnum=100000000;
longn,m,s=0,tot=0,list[maxn],p[maxn],g[maxn],gg[maxn],dis[maxn];
boolmark[maxn];
structnode
{longk,f,c,next,g;}d[maxm<<1];voidinsert(longu,longv,longc)
{d[tot].k=v;
d[tot].f=0;
d[tot].c=c;
d[tot].next=g;
g=tot;
d[tot].g=tot+1;
tot++;
d[tot].k=u;
d[tot].f=0;
d[tot].c=0;
d[tot].next=g[v];
g[v]=tot;
d[tot].g=tot-1;
tot++;}
voidbfs()
{longx,u,v,h,t;
for(longi=0;i<n;i++)
dis=0;
h=0;
t=1;
list[1]=0;
