最小費用最大流演算法證明

⑴ 圖論中 最小費用最大流演算法 結果是 同時保證費用最小和流最大么感覺怎麼可能

最小費用最大流的意思是在保證費用最少的情況下最大的流量是多少以及其路徑。不可能同時保證的。呵呵

⑵ 、圖論中最大流模型和最小費用最大流模型有什麼區別

費用不一樣。
1、最小費用最大流是指：滿足最大流的情況下，讓費用最小。
2、最小費用最大流，是在滿足上面所說的前提下，經過的路徑要最多。
3、最大流模型，費用高於後者，但是最大流模型流的路徑比它更多，覆蓋面更廣。

⑶ 最小費用最大流問題的解決方法

解決最小費用最大流問題，一般有兩條途徑。一條途徑是先用最大流演算法算出最大流，然後根據邊費用，檢查是否有可能在流量平衡的前提下通過調整邊流量，使總費用得以減少？只要有這個可能，就進行這樣的調整。調整後，得到一個新的最大流。
然後，在這個新流的基礎上繼續檢查，調整。這樣迭代下去，直至無調整可能，便得到最小費用最大流。這一思路的特點是保持問題的可行性（始終保持最大流），向最優推進。另一條解決途徑和前面介紹的最大流演算法思路相類似，一般首先給出零流作為初始流。這個流的費用為零，當然是最小費用的。然後尋找一條源點至匯點的增流鏈，但要求這條增流鏈必須是所有增流鏈中費用最小的一條。如果能找出增流鏈，則在增流鏈上增流，得出新流。將這個流做為初始流看待，繼續尋找增流鏈增流。這樣迭代下去，直至找不出增流鏈，這時的流即為最小費用最大流。這一演算法思路的特點是保持解的最優性（每次得到的新流都是費用最小的流），而逐漸向可行解靠近（直至最大流時才是一個可行解）。
由於第二種演算法和已介紹的最大流演算法接近，且演算法中尋找最小費用增流鏈，可以轉化為一個尋求源點至匯點的最短路徑問題，所以這里介紹這一演算法。
在這一演算法中，為了尋求最小費用的增流鏈，對每一當前流，需建立伴隨這一網路流的增流網路。例如圖 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)<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）。
⒊ 若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。

⑷ 演演算法Network Flow 請問如何證明尋找流量網路G=（V，E）中的最大流量，遞增路徑最多隻需要搜尋E

中國第一家-----

和引進的最大流量問題，我們舉了一個最大的材料處理流程問題。如果這個問題的已知條件，包括每條邊運輸貨物的單位成本，然後如何運輸，以獲得最大的交通和運輸成本至少嗎？這是所謂的最小費用最大流問題。
最大流量定義的基礎上，如果每個除權號C（E）的邊緣（邊緣的能力）之外的另一權重W（E）（單位流量成本）網路，並已獲得的最大流量值F ，然後最小費用最大流問題，顯然可用來描述以下的線性規劃模型：

最小ΣW（E）F（E）
E∈E

滿足0≤F（E）≤C（E），所有e∈E
F +（V）= F（V），對所有的v∈V
F +（X） = F（最大流量限制）
（或f（y）= F）

解決最小費用最大流問題，有兩個一般的方法。的方式計算的最大流量，最大流量演算法，然後基於成本的邊緣，檢查是否有可能通過調整邊緣交通流平衡的前提下，使總成本可降低？只要存在這樣的可能性，這樣的調整。調整到一個新的最大流量。
然後繼續檢查在這個新的流程的基礎上，調整。迭代下去，直到沒有調整是可能的，他們將有最小費用最大流。這一思路的特點是保持的可行性問題（始終保持最大流量）的最佳推進。的最大流量演算法思想的方式和在前面所描述的另一種解決方案是類似的，通常開始與被給定為零流量的初始流動。此流的成本是零，當然，是最小的成本。流動增值鏈，然後尋找一個源點到匯點，但這種增加的流動鏈必須是所有增量流鏈成本中最小的一個。如果他們能找到，以增加流動鏈，增加，增加流鏈，揭示了一個新的流。作為初始流的流治療，並繼續尋找增加流量鏈增加流量。本次迭代中繼續進行，直到沒有找到增加的流動鏈，當流量的最低成本的最大流量。的想法？該演算法是其特徵在於通過維持最優（每一個新的流是最小費用流），同時逐漸靠近的可行的解決方案（可達的最大流量是一個可行的解決方案）。
由於到第二演算法和最大流演算法描述的方法和演算法，以最小的成本增加流動鏈，可以轉化為求源點??到匯點的最短路徑問題，所以在這里介紹的演算法。

在該演算法中，為了尋求最小費用流鏈的增加，每個電流的流動，需要建立的網路流量網路流量不斷增加。例如，圖1 G的網路是一個具有最低成本的，邊緣的下一個參數是c（e）中，「中f（E），瓦特（E），而圖2是網路的流的增加的流網路G'。網路的頂點和原來的網路流量的增加。在網路邊緣增加流量按以下原則：如果G邊（u，v）的交通是不完整的，即F（U，V??） 0，G'CCT邊（V ，U）授權W'（V，U）= W（U，V）。增加流動網路的建立，可以通過網路和源點的最短路徑，匯點，這決定增加流動路徑，這條路徑在原有的網路流量增加。使用還增加了流動原則的最大流演算法，最小費用流鏈的增加，增加了流動CD必須選擇。
計算需要解決的一個問題。這是一個在流網路G'負側增加，並且因此不能被直接施加到找到的最短路徑x到y的標記方法，使用其他方法計算網路的最短路徑的負側，以找到的最短路徑x到y，將極大地減少了計算效率。不過標簽的方法來計算最短路徑，增加的流量每次你創建了一個網路獲得的最短路徑，在網路G的權重w（E）做了修正，不會出現消極的一面，建立增加流動網路，最短路徑不會改變。下面是這種方法。
時的流量值為零，第一建增流網路的最短路徑，由於負側的情況下，當然，可以用標記的方法來計算。之後，以建立一個提高網路消極的一面，採取的方法流邊（F（E）> 0）的權利W（E）的G修正0。為此，每增加流動網路獲得的最短路徑，下面的公式為y =-L G新的邊權重W（U，V）：

W（U，V）X（V） L（U）+ W（U V）（*）

其中，L（U），L（V） - G'最短路徑計算時，u和v的數值。首先計算最短路徑，如果（U，V）的流路側，根據最短路徑演算法必須有L（V）= L（U）+ W（U，V）= L（U ）+ W（U，V），成（*），必須

瓦特「（U，V）= 0。

（U，V）不增加流動路徑上的優勢，你必須具備：
L.（V）≤L（U）+ W（U，V） BR />代（*）W（U，V）≥0。

可見瓦特（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的最短路徑是不是由於瓦特（五）的變化的校正。

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）（V，U）W'= W（U，V）。
3。 G'有沒有的路徑x，Y G流的最小費用最大流的
停止計算，否則標記方法，找到最短的路徑P x到y。
4。 P增加G流：每邊的P（U，V），如果G（U，V），（U，V）的流量，如果G（V，U）（V，U）是流。增加（減少）的流量應確保任一側上的c（五）≥（五）≥0。
5。根據計算出的最短路徑的每個頂點的標簽值L（V），下面的公式多少G的所有邊緣的權重w（五）：

L（U） - L（ V）+ W（E）→W（E）。

6。新的數據流作為初始流動開啟2。
-----------------的
======================
>下面是英語-----

最大流問題的介紹中，我們列出了一個流量最大的貨物配送。如果這個問題還包括已知的條件下，各單位的交付貨物的成本，那麼如何運輸到最低限度，以獲得最多的流量，和運輸成本？這是所謂的最大流問題的最低成本。
最大流量的基礎上，定義，如果雙方的第一優先受償權數C（E）（即邊緣的能力），但也有另一權重W（E）（單位成本流），並一直在尋求最大的網路流量F值，然後最小費用最大流問題，它是清除下面的線性規劃模型可以用來描述如下：

最小ΣW（ E）F（E）
?∈E

滿足0≤F（E）≤C（E），所有e∈E
F +（V）= F - （V），對所有的v∈V
F +（X）= F（最大流量限制）
（或F-（Y）= F）

]演算法思想

解決最小費用最大流問題，一般有兩種方式。一種方法是使用的最大流量的演算法來計算的最大流量，然後根據在成本方面，檢查它是否可以平衡流的流量調節側，這樣就降低總成本嗎？只要存在這樣的可能性，在這種調整。調整後的新的最大流量。
然後，新的流的基礎上，繼續檢查和調整。迭代下去，直到沒有調整可能，他們將有最小費用最大流。這一思路的特點是保持的可行性問題（始終保持最大流量），以促進最佳。到另一個解決方案，並在前面的最大流演算法，介紹了類似的思路，首先，由於作為初始零流的一般流程。的流量為零的成本，當然，成本是最小的。 ，然後找到一個源到匯點的流鏈，這條產業鏈的要求，必須是一個流的全產業鏈成本最低。如果我們能找到的流程鏈，鏈中的流動，增加流量，一個新的流。將被視為初始流的流動，繼續通過增加流的搜索鏈接。此迭代下去，直到發現通過流鏈，則該流程是最小費用最大流。 ？的特點，該演算法的理念是保持最佳的解決方案（每個新的收費標準是最小的流），但逐漸接近可行的解決方案（最大流量是一個可行的解決方案時）。
第二種演算法的結果，並引進的最大流演算法發現的最小費用流鏈的演算法，可以變成一個源到匯點的最短路徑，因此該演算法在這里。

在該演算法中，為了尋求增加最小費用流鏈，目前流通的每一個陪同下，需要建立一個網路流的流量網路。例如，圖1是網路G的最小費用流，旁邊的參數C（E），F（E），W（E），圖2是網路流量的流網路G'。由峰值流作為原來的網路的網路和相同的。通過下面的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「（U，V）：通過以下方式獲得的流網路

瓦特」（U，V）= ?（U）L（V）+ W（U，V）（*）

L（U），L（V） - G'的最短路徑x到y的計算時u和v的值的標簽。最短路徑（U，V）的第一時間，如果是由邊緣的流路，然後，根據最短路徑演算法必須具有L（ⅴ）= 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）= - 瓦特（U，V）= 0，即，右側將不會是一個負側。
另外，每次迭代的計算與（*）修復了所有的w（五），它是不難證明每個路徑x到y，它的所有相同的增加路徑長度L（x）的L（y）的，因此，x和y不會是最短路徑為w（e）該修正變化。 / a>
] [計算步驟

在網路G = [V，E，C，W]，初始值是零流。
2。陪同這流網路G'= [V'，E'W'。
G'的頂點G：V'= V
如果F（U，V??）中的G 0，則（U，V），然後在建築物的邊緣G'（U，V），W（U，V）= W（U，V）。
G'建設邊（V，U），W（V，U）= - W（U，V）。
3。如果G'X到Y的路徑不存在，則G是最大流量，最小費用流
要停止計算;否則標記方法，用來找到x到y的最短路徑P.
4。據至P，G中的流量增加：每個邊緣的P （U，V），如果?（U，V），（U，V）流，如果G（V，U）（V，U），由流動增加（減少）的流量應任一側上，以確保有是c（五）≥（五）≥0。
5。根據計算的最短路徑的標簽L的峰值的時間（v）中，按G型的所有邊的權重W（E）：

L（U）（V）-L + W（E）→W（E）。
6。新的流作為初始流量為2。=========

希望能滿足您的要求----

⑸ 運籌學，最小費用最大流問題。

不必那麼麻煩，用excel規劃求解，解決此類配送問題，就是幾個按鍵的事輕松搞定。

不懂可以網路HI我。

規劃問題專家，輕松幫你搞定規劃。

⑹ 高分：網路流問題

一、引言

網路流演算法是一種高效實用的演算法，相對於其它圖論演算法來說，它的模型更加復雜，編程復雜度也更高。但是它綜合了圖論中的其它一些演算法（如最短路徑、寬度搜索演算法），因而適用范圍也更廣，經常能夠很好地解決一些搜索與動態規劃無法解決的非np問題。
網路流在具體問題中的應用，最具挑戰性的部分是模型的構造，它沒用現成的模式可以套用，需要我們對各種網路流的性質了如指掌（比如點有容量、容量有上下限、多重邊等等），根據具體的問題發揮我們的創造性。一道問題經常可以建立多種模型，不同的模型對問題的解決效率的影響也是不同的，本文通過實例探討如何確定適當的模型，提高網路流演算法的效率。

二、網路流演算法時間效率

當我們確定問題可以使用最大流演算法求解後，就根據常用的ford-fulkerson標號法求解；而最小（大）費用最大流問題也可用類似標號法的對偶演算法解題。ford-fulkerson標號法的運行時間為o（ve2），對偶法求最小費用流的運行時間大約為o（v3e2）。

顯然，影響網路流演算法的時間效率的因素主要是網路中頂點的數目與邊的數目。這二個因素之間不是相互獨立的，而是相互聯系，矛盾而統一的。在構造網路模型中，有時，實現了某個因素的優化，另外一個因素也隨之得到了優化；有時，實現某個因素的優化卻要以增大另一因素為代價。因此，我們在具體問題的解決中，要堅持"全局觀"，實現二者的平衡。

三、模型的優化與選擇

(一)減少模型的頂點數與邊數，優化模型

如果能根據問題的一些特殊性質，減少網路模型中的頂點的數目和邊的數目，則可以大大提高演算法的效率。

例1：最少皇後控制

在國際象棋中，皇後能向八個方向攻擊（如圖1(a)所示，圖中黑點格子為皇後的位置，標有k的格子為皇後可攻擊到的格子）。現在給定一個m*n（n、m均不大於於50）的棋盤，棋盤上某些格子有障礙。每個皇後被放置在無障礙的格子中，它就控制了這個格子，除此，它可以從它能攻擊到的最多8個格子中選一個格子來控制，如圖1(b)所示，標號為1的格子被一個皇後所控制。

請你編一程序，計算出至少有多少個皇後才能完全控制整個棋盤。

圖1(a) 圖1(b)

輸入格式：
輸入文件的第一行有兩個整數m和n，表示棋盤的行數與列數。接下來m行n列為一個字元矩陣，用''.''號表示空白的格子，''x''表示有障礙的格子。

輸出格式：
輸出文件的第一行僅有一個數s，表示需要皇後的數目。
sample input
3 4
x...
x.x.
.x..
sample ouput
5

問題分析]

如果本問題用簡單的搜索來做，由於題目給的棋盤很大，搜索演算法很難在短時間內出解。由於一個皇後在棋盤最多隻能控制兩個格子，因此最少需要的皇後數目的下界為[n*m/2]。要使得皇後數目最少，必定是盡量多的皇後控制兩個格子。如果我們在每兩個能相互攻擊到的格子之間加上一條有向弧，則問題很類似於二分圖的最大匹配問題。

[模型一]

1． 將每個非障礙的格子按行優先編號(0~m*n-1)。
2． 將上述的每個格子i折成兩個格子i''和i''''，作為網路模型中的頂點。
3． 若格子i可以攻擊到格子j且i<j，則在模型中頂點i''到j''''之間加上一條有向弧，容量為1。
4． 增加一個源點s，從s點向所有頂點i''添上一條弧；增加一個匯點t，從所有頂點j''''到t添上一條弧，容量均為1。

圖1(b)所示的棋盤，對應的模型為：

圖2

顯然，任一解對應於以上模型的一個最大匹配。且最大匹配中，匹配數必定是偶數。因此至少需要的馬匹數為m＊n－障礙數－最大匹配數/2。

[模型二]

如果我們將棋盤塗成黑白相間的格子，則某皇後控制的兩個格子一定是一個是黑格，另一個是白格（如圖3），不妨設這兩個格子中皇後在白格子上。於是，我們將n*m個格子分成兩部分白格與黑格。因此我們可以將模型一優化為：

圖3

1．將棋盤中的所有格子分成兩個部分，對所有的格子進行編號，每個白格與它能攻擊到的黑格之間（障礙除外）添上一條從白格到黑格的弧，構成一個二分圖。

2．增加一個源點s，從s點向所有非障礙的白格添上一條弧；增加一個匯點t，從所有非障礙的黑格到t添上一條弧。

3．設置所有的弧的流量為1。
圖1(b)所示的棋盤，對應的模型為：

圖4

[兩種模型的比較]

顯然，模型二的頂點數與邊數大致是模型一的一半。下面是在bp環境下兩種模型的時間效率比較(p166/32m)：

模型一 模型二

可擴展性 不易列印出一種解 容易列印出一種解

模型二正是根據問題的特殊性（即馬的走法），將網格中的格點分成白與黑兩類，且規定馬只能從白格跳到黑格，從而避免將每個格點折分成兩個點，減少模型的頂點數，同時也大大減少了邊的數目。達到了很好的優化效果。

(二)綜合各種模型的優點，智能選擇模型

有時，同一問題的各種模型各有特色，各有利弊。這種情況下，我們就要綜合考慮各種模型的優缺點，根據測試數據智能地選擇問題的模型。

例2火星探測器（ioi97）

有一個登陸艙（pod），里邊裝有許多障礙物探測車（mev），將在火星表面著陸。著陸後，探測車離開登陸艙向相距不遠的先期到達的傳送器（transmitter）移動，mev一邊移動，一邊採集岩石（rock）標品，岩石由第一個訪問到它的mev所採集，每塊岩石只能被採集一次。但是這之後，其他mev可以從該處通過。探測車mev不能通過有障礙的地面。
本題限定探測車mev只能沿著格子向南或向東從登陸處向傳送器transmitter移動，允許多個探測車mev在同一時間占據同一位置。

任務：計算出所有探測車的移動途徑，使其送到傳送器的岩石標本的數量最多，且使得所有的探測車都必須到達傳送器。

輸入：

火星表面上的登陸艙pod和傳送器之間的位置用網路p和q表示，登陸艙pod的位置為（1，1）點，傳送器的位置在（p，q）點。

火星上的不同表面用三種不同的數字元號來表示：

0代表平坦無障礙
1代表障礙
2代表石塊。
輸入文件的組成如下：
numberofvehicles
p
q
(x1y1)(x2y1)(x3,y1)…(xp-1y1)(xpy1)
(x1y2)(x2y2)(x3,y2)…(xp-1y1)(xpy2)
(x1y3)(x2y3)(x3,y3)…(xp-1y3)(xpy3)
…
(x1yq-1)(x2yq-1)(x3,yq-1)…(xp-1yq-1)(xpyq-1)
(x1yq)(x2yq)(x3,yq)…(xp-1yq)(xpyq)
p和q是網路的大小；numberofvehicles是小於1000的整數，表示由登陸艙pod所開出的探測車的個數。共有q行數據，每行表示火星表面的一組數據，p和q都不超過128。

[模型一]

很自然我們以登陸艙的位置為源點，傳送器的位置為匯點。同時某塊岩石由第一個訪問到它的mev所採集，每塊岩石只能被採集一次。但是這之後，其他mev可以從該處通過，且允許多個探測車mev在同一時間占據同一位置。因此我們將地圖中的每個點分成兩個點，即（x,y）à(x,y,0)和(x,y,1)。具體的描述一個火星地圖的網路模型構造如下：

1． 將網格中的每個非障礙點分成(x,y)兩個點(x,y,0)和(x,y,1)，其中源點s = v(1, 1, 0),匯點t = v(maxx, maxy, 1)。

2． 在以上頂點中添加以下三種類型的邊e1,e2,e3，相應地容量和費用分別記為c1、c2、c3以及w1、w2、w3:

u e1 = v(x, y, 0) -> v(x, y, 1),c1 = maxint,w1 = 0。
u e2 = v(x, y, 0) -> v(x, y, 1)，c2 = 1，w2 = -1（這里要求(x, y)必須是礦石）
u e3 = v(x, y, 1) -> v(x'', y'', 0)，c3 = maxint,w3 = 0.

其中x''=x+1 y''=y 或x''=x y''=y+1,1 <= x'' <= maxx，1 <= y'' <= maxy，且(x'' y'')非障礙。

從以上模型中可以看出，在構造的過程中，將地圖上的一個點"拆"成了網路的兩個節點。添加e1型邊使得每個點可以被多次訪問，而添加e2型邊使得某點上的礦石對於這個網路，從s到t的一條路徑可以看作是一輛探測車的行動路線。路徑費用就是探測車搜集到的礦石的數目。對於網路g求流量為numberofvehicles的固定最小費用流，可以得到問題的解。

[模型二]

事實上，如果我們只考慮這numberofvehicles輛車中每輛車分別依次裝上哪些礦石。則每輛車經過的礦石就是一條流，因此我們以網格中的礦石為網路的頂點建立以下的網路流模型。

1. 將網格中的每個起點(網格左上角)能到達，且能從它能到達終點(右下角)的礦石 (x,y)點分成左點(x,y,0)和右點(x,y,1)兩個點，並添加源點s和匯點t。
2. 在以上頂點中添加以下五種類型的邊e1,e2,e3，相應地容量和費用分別記為c1、c2、c3以及w1、w2、w3:

u e1 = v(x, y, 0) -> v(x, y, 1),c1 = 1,w1 = -1。
u e2 = v(x, y, 1) -> v(x'', y'', 0)，c2 = 1，w2 = 0（礦石點(x, y)可到達礦石點(x'',y'')）。
u e3 = s -> v(x, y, 0)，c3 = 1,w3 = 0。
u e4 = v(x, y, 1)->t，c4 = 1,w4 = 0。
u e5=s->t,c5=maxint,w5=0。

由於每個石塊被折成兩個點，且容量為1，就保證了每個石塊只被取走一次，同時取走一塊石塊就得到-1的費用。因此對以上模型，我們求流量為numberofvehicles的最小費用流，就可得到解。

[兩種模型的比較]

1.模型一以網格為頂點，模型二以礦石為頂點，因此在頂點個數上模型二明顯優於模型一，對於一些礦石比較稀疏，而網格又比較大的數據，模型二的效率要比模型一來得高。且只要礦石的個數不超過一定數目，模型二可以處理p，q很大的數據，而模型一卻不行。

2．模型一中邊的數目最多為3*p*q，而模型二中邊的數目最壞情況下大約為p*q*(p+1)*(q+1)/4-p*q。因此在這個問題中，若對於一些礦石比較密集且網格又比較大的數據，模型二的邊數將大大超過模型一，從而使得時間效率大大低於模型一。

下面是網格中都是礦石的情況比較（piii700/128m ，bp7.0保護模式）：
numberofvehicles＝10 模型一 模型二

通過以上數據，可知對於p，q不超過60的情況，模型一都能在10秒內出解。而模型二則對於p、q＝30的最壞情況下速度就很慢了，且p、q超過30後就出現內存溢出情況，而無法解決。

因此，對於本題，以上兩種模型各有利弊，我們可根據測試數據中礦石稀疏程度來決定建立什麼樣的模型。若礦石比較稀疏，則可以考慮用建立如模型二的網路模型；若礦石比較密集則建立模型一所示網路模型。然後，再應用求最小費用最大流演算法求解。對於p，q＞60，且礦石比較多情況下，兩種模型的網路流演算法都無法求解。在實際的應用中問題經常都只要求近似解，此時還可用綜合一些其它演算法來求解。

四、結束語

綜上所述，網路流演算法中模型的優化是網路流演算法提高效率的根本。我們要根據實際問題，從減少頂點及邊的角度綜合考慮如何對模型進行優化，選擇適當的模型，以提高演算法的效率。對於有些題目，解題的各種模型各有優劣時，還可通過程序自動分析測試數據，以決定何種情況下採用何種模型，充分發揮各種模型的優點，以達到優化程序效率的目的。

⑺ 最小費用最大流問題的介紹

最小費用最大流問題是經濟學和管理學中的一類典型問題。在一個網路中每段路徑都有「容量」和「費用」兩個限制的條件下，此類問題的研究試圖尋找出：流量從A到B，如何選擇路徑、分配經過路徑的流量，可以在流量最大的前提下，達到所用的費用最小的要求。如n輛卡車要運送物品，從A地到B地。由於每條路段都有不同的路費要繳納，每條路能容納的車的數量有限制，最小費用最大流問題指如何分配卡車的出發路徑可以達到費用最低，物品又能全部送到。

⑻ 最小費用流和最小費用最大流有什麼區別

最小費用最大流是指：滿足最大流的情況下，讓費用最小。
最小費用流：僅要求費用最小，通常情況下有費用為負的邊權(如果費用全為正，那麼可以讓流量為0，費用也就是0)，可以使用最小費用最大流的演算法求解，只不過終止條件變為「從原點到匯點的費用為正」
最小費用最大流演算法的原本終止條件為「從原點到匯點的容量為0」

⑼ 關於最小費用最大流

const
maxn=100;
maxq=100000;

var
p,c,f:array[1..maxn,1..maxn] of longint;
dist,path:array[1..maxn] of longint;
q:array[1..maxq] of longint;
check:array[1..maxn] of 0..1;
n,m:longint;
mark:boolean;

procere init;
var
s,t,r,w,i,j:longint;
begin
readln (n);
readln (m);
for i:=1 to m do begin
readln (s,t,r,w);
c[s,t]:=r;p[s,t]:=w;
end;
end;

procere main;
var
i,j,a,r,l,k:longint;
begin
fillchar(f,sizeof(f),0);
mark:=true;
while mark do begin
q[1]:=1;r:=0;l:=1;
mark:=false;
for i:=2 to n do dist[i]:=maxlongint;
fillchar(check,sizeof(check),0);dist[1]:=0;
fillchar(path,sizeof(path),0);
while r<l do begin
inc(r);
for i:=2 to n do if (c[i,q[r]]<>0) or (c[q[r],i]<>0) then begin
if (c[q[r],i]<>0) and (f[q[r],i]<c[q[r],i]) and (dist[q[r]]+p[q[r],i]<dist[i]) then begin
dist[i]:=dist[q[r]]+p[q[r],i];
path[i]:=q[r];
if check[i]=0 then begin inc(l);q[l]:=i;check[i]:=1;end;
end;
if (c[i,q[r]]<>0) and (f[i,q[r]]<>0) and (dist[q[r]]-p[i,q[r]]<dist[i]) then begin
dist[i]:=dist[q[r]]-p[i,q[r]];
path[i]:=-q[r];
if check[i]=0 then begin inc(l);q[l]:=i;check[i]:=1;end;
end;
end;
check[q[r]]:=0;
end;
if path[n]<>0 then begin
mark:=true;
l:=n;a:=maxlongint;
while l<>1 do begin
k:=abs(path[l]);
if path[l]>0 then begin
if c[k,l]-f[k,l]<a then a:=c[k,l]-f[k,l];
end
else begin
if f[l,k]<a then a:=f[l,k];
end;
l:=k;
end;
l:=n;
while l<>1 do begin
k:=abs(path[l]);
if path[l]>0 then inc(f[k,l],a)
else dec(f[l,k],a);
l:=k;
end;
end;
end;
end;

procere print;
var
i,j,s:longint;
begin
s:=0;for i:=1 to n-1 do inc(s,f[i,n]);
writeln (s);
s:=0;
for i:=1 to n do
for j:=1 to n do inc(s,f[i,j]*p[i,j]);
writeln (s);
end;

begin
init;
main;
print;
end.

最小費用最大流。

你的好長啊。···

把程序看懂後自己可以化嘛。
我暫時找不到用邊存儲的題目。 化為邊後不小心錯了也有可能。