網絡流算法是壹種高效實用的算法，相對於其它圖論算法來說，它的模型更加復雜，編程復雜度也更高。但是它綜合了圖論中的其它壹些算法（如最短路徑、寬度搜索算法），因而適用範圍也更廣，經常能夠很好地解決壹些搜索與動態規劃無法解決的非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，且礦石比較多情況下，兩種模型的網絡流算法都無法求解。在實際的應用中問題經常都只要求近似解，此時還可用綜合壹些其它算法來求解。
四、結束語
綜上所述，網絡流算法中模型的優化是網絡流算法提高效率的根本。我們要根據實際問題，從減少頂點及邊的角度綜合考慮如何對模型進行優化，選擇適當的模型，以提高算法的效率。對於有些題目，解題的各種模型各有優劣時，還可通過程序自動分析測試數據，以決定何種情況下采用何種模型，充分發揮各種模型的優點，以達到優化程序效率的目的。