最小費用最大流問題是經濟學和管理學中的一類典型問題。在一個網路中每段路徑都有“容量”和“費用”兩個限制的條件下，此類問題的研究試圖尋找出：流量從A到B，如何選擇路徑、分配經過路徑的流量，可以在流量最大的前提下，達到所用的費用最小的要求。如n輛卡車要運送物品，從A地到B地。由於每條路段都有不同的路費要繳納，每條路能容納的車的數量有限制，最小費用最大流問題指如何分配卡車的出發路徑可以達到費用最低，物品又能全部送到。
基本介紹
- 中文名：最小費用最大流
- 外文名： minimum cost maximum flow(MCMF)
- 範疇：經濟學和管理學
- 限制的條件：容量和費用
- 相關定義：前向弧和後向弧
相關定義,解決方法,算法舉例,
相關定義
前向弧和後向弧
在網路D(V,A) 中,如果對連線發點vs和收點vt 的一條鏈P，方向規定為從vs 到vt，則當鏈P 中弧(vi,vj)
的方向與規定的方向一致時，稱弧（vi,vj) 為前向弧，否則稱為後向弧。不在這條鏈上的弧，不定義前向弧和後向弧。
可擴充鏈
設{fij}為一可行流（假設為非負值），如果存在從發點vs 到收點vt 的鏈P，在鏈P 上，下列兩條同時滿足，則稱P 為可擴充鏈：
①對於戒采P 上的前向弧（vi,vj) 有fij
②對於P 上的後向弧（vi,vj) 有fij>0。
可擴充鏈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）的修正而發生變化。
【計算步驟】
⒈ 對網路G=[V,E,C,W]，給出流值為零的初始流。
⒉ 作伴隨這個流的增流網路G′=[V′，E′，W′]。G′的頂點同G：V′=V。若G中f(u,v)0，則G′中建邊（v,u），w′（v,u)=-w(u,v）。
⒊ 若G′不存在x至y的路徑，則G的流即為最小費用最大流， 停止計算；否則用標號法找出x至y的最短路徑P。
⒋ 根據P，在G上增流：對P的每條邊（u,v），若G存在（u,v），則（u,v）增流；若G存在（v,u），則（v,u）減流。增（減）流後，應保證對任一邊有c(e）≥ f(e）≥0。
⒌ 根據計算最短路徑時的各頂點的標號值L(v），按下式修 改G一切邊的權數w(e):
L(u)-L(v)+w(e）→w(e）。
⒍ 將新流視為初始流，轉2。
算法舉例
augmentpath
譯為“增廣路”算法，其思想大致如下：
原有網路為G，設有一輔助圖G'，其定義為V(G') = V(G），E(G'）初始值（也就是容量）與E(G）相同。每次操作時從Source點搜尋出一條到Sink點的路徑，然後將該路徑上所有的容量減去該路徑上容量的最小值，然後對路徑上每一條邊；添加或擴大反方向的容量，大小就是剛才減去的容量。一直到沒有路為止。此時輔助圖上的正向流就是最大流。
我們很容易覺得這個算法會陷入死循環，但事實上不是這樣的。我們只需要注意到每次網路中由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），還有一個叫Highest Label Preflow Push的算法複雜度據說是O(V^2*E^0.5）。我研究了一下HLPP，感覺它和Relabel-to-Front本質上沒有區別，因為Relabel-to-Front每次前移的都是高度最高的頂點，所以也相當於每次選擇最高的標號進行更新。還有一個感覺也會很好實現的算法是使用佇列維護溢出頂點，每次對pop出來的頂點discharge，出現了新的溢出頂點時入隊。
Push-Relabel類的算法有一個名為gap heuristic的最佳化，就是當存在一個整數0k的頂點v做更新，若它小於V+1就置為V+1。
c++程式舉例
typedef pair<int,int> P;
struct edge { int to,cap,cost,rev; };
int V;
vector<edge> G[MAX_V];
int h[MAX_V];
int dist[MAX_V];
int prevv[MAX_V],preve[MAX_V];
void add_edge(int from,int to,int cap,int cost) {
G[from].push_back((edge){to,cap,cost,G[to].size()});
G[to].push_back((edge){from,0,-cost,G[from].size()-1});
}
int min_cost_flow(int s,int t,int f) {
int res;
fill(h,h+V,0);
while(f>0) {
priority_queue<P,vector<P>,greater<P> > que;
fill(dist,dist+V,INF);
dist[s]=0;
que.push(P(0,s));
while(!que.empty()) {
P p=que.top();que.pop();
int v=p.second;
if(dist[v]<p.first) continue;
for(int i=0;i<G[v].size();i++) {
edge &e=G[v][i];
if(e.cap>0&&dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]) {
dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
prevv[e.to]=v;
preve[e.to]=i;
que.push(P(dist[e.to],e.to));
}
}
}
if(dist[t]==INF) return -1;
for(int v=0;v<V;v++) h[v]+=dist[v];
int d=f;
for(int v=t;v!=s;v=prevv[v])
d=min(d,G[prevv[v]][preve[v]].cap);
f-=d;
res+=d*h[t];
for(int v=t;v!=s;v=prevv[v]) {
edge &e=G[prevv[v]][preve[v]];
e.cap-=d;
G[v][e.rev].cap+=d;
}
}
return res;
}
計算中有一個問題需要解決。這就是增流網路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）的修正而發生變化。
【計算步驟】
⒈ 對網路G=[V,E,C,W]，給出流值為零的初始流。
⒉ 作伴隨這個流的增流網路G′=[V′，E′，W′]。G′的頂點同G：V′=V。若G中f(u,v)0，則G′中建邊（v,u），w′（v,u)=-w(u,v）。
⒊ 若G′不存在x至y的路徑，則G的流即為最小費用最大流， 停止計算；否則用標號法找出x至y的最短路徑P。
⒋ 根據P，在G上增流：對P的每條邊（u,v），若G存在（u,v），則（u,v）增流；若G存在（v,u），則（v,u）減流。增（減）流後，應保證對任一邊有c(e）≥ f(e）≥0。
⒌ 根據計算最短路徑時的各頂點的標號值L(v），按下式修 改G一切邊的權數w(e):
L(u)-L(v)+w(e）→w(e）。
⒍ 將新流視為初始流，轉2。
算法舉例
augmentpath
譯為“增廣路”算法，其思想大致如下：
原有網路為G，設有一輔助圖G'，其定義為V(G') = V(G），E(G'）初始值（也就是容量）與E(G）相同。每次操作時從Source點搜尋出一條到Sink點的路徑，然後將該路徑上所有的容量減去該路徑上容量的最小值，然後對路徑上每一條邊；添加或擴大反方向的容量，大小就是剛才減去的容量。一直到沒有路為止。此時輔助圖上的正向流就是最大流。
我們很容易覺得這個算法會陷入死循環，但事實上不是這樣的。我們只需要注意到每次網路中由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），還有一個叫Highest Label Preflow Push的算法複雜度據說是O(V^2*E^0.5）。我研究了一下HLPP，感覺它和Relabel-to-Front本質上沒有區別，因為Relabel-to-Front每次前移的都是高度最高的頂點，所以也相當於每次選擇最高的標號進行更新。還有一個感覺也會很好實現的算法是使用佇列維護溢出頂點，每次對pop出來的頂點discharge，出現了新的溢出頂點時入隊。
Push-Relabel類的算法有一個名為gap heuristic的最佳化，就是當存在一個整數0k的頂點v做更新，若它小於V+1就置為V+1。
c++程式舉例
typedef pair<int,int> P;
struct edge { int to,cap,cost,rev; };
int V;
vector<edge> G[MAX_V];
int h[MAX_V];
int dist[MAX_V];
int prevv[MAX_V],preve[MAX_V];
void add_edge(int from,int to,int cap,int cost) {
G[from].push_back((edge){to,cap,cost,G[to].size()});
G[to].push_back((edge){from,0,-cost,G[from].size()-1});
}
int min_cost_flow(int s,int t,int f) {
int res;
fill(h,h+V,0);
while(f>0) {
priority_queue<P,vector<P>,greater<P> > que;
fill(dist,dist+V,INF);
dist[s]=0;
que.push(P(0,s));
while(!que.empty()) {
P p=que.top();que.pop();
int v=p.second;
if(dist[v]<p.first) continue;
for(int i=0;i<G[v].size();i++) {
edge &e=G[v][i];
if(e.cap>0&&dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]) {
dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
prevv[e.to]=v;
preve[e.to]=i;
que.push(P(dist[e.to],e.to));
}
}
}
if(dist[t]==INF) return -1;
for(int v=0;v<V;v++) h[v]+=dist[v];
int d=f;
for(int v=t;v!=s;v=prevv[v])
d=min(d,G[prevv[v]][preve[v]].cap);
f-=d;
res+=d*h[t];
for(int v=t;v!=s;v=prevv[v]) {
edge &e=G[prevv[v]][preve[v]];
e.cap-=d;
G[v][e.rev].cap+=d;
}
}
return res;
}
