網路流演算法的應用

Ⅰ 家園 網路流拆點 pascal

】動態規劃 階段

動態規劃是信息學競賽中的常見演算法，本文的主要內容就是分析它的特點。
文章的第一部分首先探究了動態規劃的本質，因為動態規劃的特點是由它的本質所決定的。第二部分從動態規劃的設計和實現這兩個角度分析了動態規劃的多樣性、模式性、技巧性這三個特點。第三部分將動態規劃和遞推、搜索、網路流這三個相關演算法作了比較，從中探尋動態規劃的一些更深層次的特點。
文章在分析動態規劃的特點的同時，還根據這些特點分析了我們在解題中應該怎樣利用這些特點，怎樣運用動態規劃。這對我們的解題實踐有一定的指導意義。

動態規劃是編程解題的一種重要的手段，在如今的信息學競賽中被應用得越來越普遍。最近幾年的信息學競賽，不分大小，幾乎每次都要考察到這方面的內容。因此，如何更深入地了解動態規劃，從而更為有效地運用這個解題的有力武器，是一個值得深入研究的問題。
要掌握動態規劃的應用技巧，就要了解它的各方面的特點。首要的，是要深入洞悉動態規劃的本質。
§1動態規劃的本質
動態規劃是在本世紀50年代初，為了解決一類多階段決策問題而誕生的。那麼，什麼樣的問題被稱作多階段決策問題呢？
§1.1多階段決策問題
說到多階段決策問題，人們很容易舉出下面這個例子。
[例1] 多段圖中的最短路徑問題：在下圖中找出從A1到D1的最短路徑。
仔細觀察這個圖不難發現，它有一個特點。我們將圖中的點分為四類（圖中的A、B、C、D），那麼圖中所有的邊都處於相鄰的兩類點之間，並且都從前一類點指向後一類點。這樣，圖中的邊就被分成了三類（AàB、BàC、CàD）。我們需要從每一類中選出一條邊來，組成從A1到D1的一條路徑，並且這條路徑是所有這樣的路徑中的最短者。
從上面的這個例子中，我們可以大概地了解到什麼是多階段決策問題。更精確的定義如下：
多階段決策過程，是指這樣的一類特殊的活動過程，問題可以按時間順序分解成若干相互聯系的階段，在每一個階段都要做出決策，全部過程的決策是一個決策序列[1]。要使整個活動的總體效果達到最優的問題，稱為多階段決策問題。
從上述的定義中，我們可以明顯地看出，這類問題有兩個要素。一個是階段，一個是決策。
§1.2階段與狀態
階段：將所給問題的過程，按時間或空間特徵分解成若干相互聯系的階段，以便按次序去求每階段的解。常用字母k表示階段變數。[1]
階段是問題的屬性。多階段決策問題中通常存在著若干個階段，如上面的例子，就有A、B、C、D這四個階段。在一般情況下，階段是和時間有關的；但是在很多問題（我的感覺，特別是信息學問題）中，階段和時間是無關的。從階段的定義中，可以看出階段的兩個特點，一是「相互聯系」，二是「次序」。
階段之間是怎樣相互聯系的？就是通過狀態和狀態轉移。
狀態：各階段開始時的客觀條件叫做狀態。描述各階段狀態的變數稱為狀態變數，常用sk表示第k階段的狀態變數，狀態變數sk的取值集合稱為狀態集合，用Sk表示。[1]
狀態是階段的屬性。每個階段通常包含若干個狀態，用以描述問題發展到這個階段時所處在的一種客觀情況。在上面的例子中，行人從出發點A1走過兩個階段之後，可能出現的情況有三種，即處於C1、C2或C3點。那麼第三個階段就有三個狀態S3=。
每個階段的狀態都是由以前階段的狀態以某種方式「變化」而來，這種「變化」稱為狀態轉移（暫不定義）。上例中C3點可以從B1點過來，也可以從B2點過來，從階段2的B1或B2狀態走到階段3的C3狀態就是狀態轉移。狀態轉移是導出狀態的途徑，也是聯系各階段的途徑。
說到這里，可以提出應用動態規劃的一個重要條件。那就是將各階段按照一定的次序排列好之後，對於某個給定的階段狀態，它以前各階段的狀態無法直接影響它未來的發展，而只能通過當前的這個狀態。換句話說，每個狀態都是「過去歷史的一個完整總結[1]」。這就是無後效性。對這個性質，下文還將會有解釋。
§1.3決策和策略
上面的階段與狀態只是多階段決策問題的一個方面的要素，下面是另一個方面的要素——決策。
決策：當各段的狀態取定以後，就可以做出不同的決定，從而確定下一階段的狀態，這種決定稱為決策。表示決策的變數，稱為決策變數，常用uk(sk)表示第k階段當狀態為sk時的決策變數。在實際問題中，決策變數的取值往往限制在一定范圍內，我們稱此范圍為允許決策集合。常用Dk(sk)表示第k階段從狀態sk出發的允許決策集合。顯然有uk(sk) ÎDk(sk)。[1]
決策是問題的解的屬性。決策的目的就是「確定下一階段的狀態」，還是回到上例，從階段2的B1狀態出發有三條路，也就是三個決策，分別導向階段3的C1、C2、C3三個狀態，即D2(B1)=。
有了決策，我們可以定義狀態轉移：動態規劃中本階段的狀態往往是上一階段和上一階段的決策結果，由第k段的狀態sk和本階段的決策uk確定第k+1段的狀態sk+1的過程叫狀態轉移。狀態轉移規律的形式化表示sk+1=Tk(sk,uk)稱為狀態轉移方程。
這樣看來，似乎決策和狀態轉移有著某種聯系。我的理解，狀態轉移是決策的目的，決策是狀態轉移的途徑。
各段決策確定後，整個問題的決策序列就構成一個策略，用p1,n=表示。對每個實際問題，可供選擇的策略有一定范圍，稱為允許策略集合，記作P1,n，使整個問題達到最有效果的策略就是最優策略。[1]
說到這里，又可以提出運用動態規劃的一個前提。即這個過程的最優策略應具有這樣的性質：無論初始狀態及初始決策如何，對於先前決策所形成的狀態而言，其以後的所有決策應構成最優策略[1]。這就是最優化原理。簡言之，就是「最優策略的子策略也是最優策略」。
§1.4最優化原理與無後效性
這里，我把最優化原理定位在「運用動態規劃的前提」。這是因為，是否符合最優化原理是一個問題的本質特徵。對於不滿足最優化原理的一個多階段決策問題，整體上的最優策略p1,n同任何一個階段k上的決策uk或任何一組階段k1…k2上的子策略pk1,k2都不存在任何關系。如果要對這樣的問題動態規劃的話，我們從一開始所作的劃分階段等努力都將是徒勞的。
而我把無後效性定位在「應用動態規劃的條件」，是因為動態規劃是按次序去求每階段的解，如果一個問題有後效性，那麼這樣的次序便是不合理的。但是，我們可以通過重新劃分階段，重新選定狀態，或者增加狀態變數的個數等手段，來是問題滿足無後效性這個條件。說到底，還是要確定一個「序」。
在信息學的多階段決策問題中，絕大部分都是能夠滿足最優化原理的，但它們往往會在後效性這一點上來設置障礙。所以在解題過程中，我們會特別關心「序」。對於有序的問題，就會考慮到動態規劃；對於無序的問題，也會想方設法來使其有序。
§1.5最優指標函數和規劃方程
最優指標函數：用於衡量所選定策略優劣的數量指標稱為指標函數，最優指標函數記為fk(sk)，它表示從第k段狀態sk採用最優策略p*k,n到過程終止時的最佳效益值[1]。
最優指標函數其實就是我們真正關心的問題的解。在上面的例子中，f2(B1)就表示從B1點到終點D1點的最短路徑長度。我們求解的最終目標就是f1(A1)。
最優指標函數的求法一般是一個從目標狀態出發的遞推公式，稱為規劃方程：

其中sk是第k段的某個狀態，uk是從sk出發的允許決策集合Dk(sk)中的一個決策，Tk(sk,uk)是由sk和uk所導出的第k+1段的某個狀態sk+1，g(x,uk)是定義在數值x和決策uk上的一個函數，而函數opt表示最優化，根據具體問題分別表為max或min。
，稱為邊界條件。
上例中的規劃方程就是：

邊界條件為
這里是一種從目標狀態往回推的逆序求法，適用於目標狀態確定的問題。在我們的信息學問題中，也有很多有著確定的初始狀態。當然，對於初始狀態確定的問題，我們也可以採用從初始狀態出發往前推的順序求法。事實上，這種方法對我們來說要更為直觀、更易設計一些，從而更多地出現在我們的解題過程中。
我們本節所討論的這些理論雖然不是本文的主旨，但是卻對下面要說的動態規劃的特點起著基礎性的作用。
§2動態規劃的設計與實現
上面我們討論了動態規劃的一些理論，本節我們將通過幾個例子中，動態規劃的設計與實現，來了解動態規劃的一些特點。
§2.1動態規劃的多樣性
[例2] 花店櫥窗布置問題（IOI99）試題見附錄
本題雖然是本屆IOI中較為簡單的一題，但其中大有文章可作。說它簡單，是因為它有序，因此我們一眼便可看出這題應該用動態規劃來解決。但是，如何動態規劃呢？如何劃分階段，又如何選擇狀態呢？
<方法1>以花束的數目來劃分階段。在這里，階段變數k表示的就是要布置的花束數目（前k束花），狀態變數sk表示第k束花所在的花瓶。而對於每一個狀態sk，決策就是第k-1束花應該放在哪個花瓶，用uk表示。最優指標函數fk(sk)表示前k束花，其中第k束插在第sk個花瓶中，所能取得的最大美學值。
狀態轉移方程為
規劃方程為
（其中A(i,j)是花束i插在花瓶j中的美學值）
邊界條件 （V是花瓶總數，事實上這是一個虛擬的邊界）
<方法2>以花瓶的數目來劃分階段。在這里階段變數k表示的是要佔用的花瓶數目（前k個花瓶），狀態變數sk表示前k個花瓶中放了多少花。而對於任意一個狀態sk，決策就是第sk束花是否放在第k個花瓶中，用變數uk=1或0來表示。最優指標函數fk(sk)表示前k個花瓶中插了sk束花，所能取得的最大美學值。
狀態轉移方程為
規劃方程為
邊界條件為
兩種劃分階段的方法，引出了兩種狀態表示法，兩種規劃方式，但是卻都成功地解決了問題。只不過因為決策的選擇有多有少，所以演算法的時間復雜度也就不同。[2]
這個例子具有很大的普遍性。有很多的多階段決策問題都有著不止一種的階段劃分方法，因而往往就有不止一種的規劃方法。有時各種方法所產生的效果是差不多的，但更多的時候，就像我們的例子一樣，兩種方法會在某個方面有些區別。
所以，在用動態規劃解題的時候，可以多想一想是否有其它的解法。對於不同的解法，要注意比較，好的演算法好在哪裡，差一點的演算法差在哪裡。從各種不同演算法的比較中，我們可以更深刻地領會動態規劃的構思技巧。
§2.2動態規劃的模式性
這個可能做過動態規劃的人都有體會，從我們上面對動態規劃的分析也可以看出來。動態規劃的設計都有著一定的模式，一般要經歷以下幾個步驟。
劃分階段：按照問題的時間或空間特徵，把問題分為若干個階段。注意這若干個階段一定要是有序的或者是可排序的，否則問題就無法求解。
選擇狀態：將問題發展到各個階段時所處於的各種客觀情況用不同的狀態表示出來。當然，狀態的選擇要滿足無後效性。
確定決策並寫出狀態轉移方程：之所以把這兩步放在一起，是因為決策和狀態轉移有著天然的聯系，狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態。所以，如果我們確定了決策，狀態轉移方程也就寫出來了。但事實上，我們常常是反過來做，根據相鄰兩段的各狀態之間的關系來確定決策。
寫出規劃方程（包括邊界條件）：在第一部分中，我們已經給出了規劃方程的通用形式化表達式。一般說來，只要階段、狀態、決策和狀態轉移確定了，這一步還是比較簡單的。
動態規劃的主要難點在於理論上的設計，一旦設計完成，實現部分就會非常簡單。大體上的框架如下：
對f1(s1)初始化（邊界條件）
for kß2 to n（這里以順序求解為例）
對每一個skÎSk
fk(sk)ß一個極值（∞或－∞）
對每一個uk(sk)ÎDk(sk)
sk-1ßTk(sk,uk)
tßg(fk-1(sk-1),uk)
y t比fk(sk)更優 n
fk(sk)ßt
輸出fn(sn)
這個N-S圖雖然不能代表全部，但足可以概括大多數。少數的一些特殊的動態規劃，其實現的原理也是類似，可以類比出來。我們到現在對動態規劃的分析，主要是在理論上、設計上，原因也就在此。
掌握了動態規劃的模式性，我們在用動態規劃解題時就可以把主要的精力放在理論上的設計。一旦設計成熟，問題也就基本上解決了。而且在設計演算法時也可以按部就班地來。
但是「物極必反」，太過拘泥於模式就會限制我們的思維，扼殺優良演算法思想的產生。我們在解題時，不妨發揮一下創造性，去突破動態規劃的實現模式，這樣往往會收到意想不到的效果。[3]
§2.3動態規劃的技巧性
上面我們所說的動態規劃的模式性，主要指的是實現方面。而在設計方面，雖然它較為嚴格的步驟性，但是它的設計思想卻是沒有一定的規律可循的。這就需要我們不斷地在實踐當中去掌握動態規劃的技巧，下面僅就一個例子談一點我自己的體會。
[例3] 街道問題：在下圖中找出從左下角到右上角的最短路徑，每步只能向右方或上方走。
這是一道簡單而又典型的動態規劃題，許多介紹動態規劃的書與文章中都拿它來做例子。通常，書上的解答是這樣的：

按照圖中的虛線來劃分階段，即階段變數k表示走過的步數，而狀態變數sk表示當前處於這一階段上的哪一點（各點所對應的階段和狀態已經用ks在地圖上標明）。這時的模型實際上已經轉化成了一個特殊的多段圖。用決策變數uk=0表示向右走，uk=1表示向上走，則狀態轉移方程如下：

（這里的row是地圖豎直方向的行數）
我們看到，這個狀態轉移方程需要根據k的取值分兩種情況討論，顯得非常麻煩。相應的，把它代入規劃方程而付諸實現時，演算法也很繁。因而我們在實現時，一般是不會這么做的，而代之以下面方法：
將地圖中的點規則地編號如上，得到的規劃方程如下：

（這里Distance表示相鄰兩點間的邊長）
這樣做確實要比上面的方法簡單多了，但是它已經破壞了動態規劃的本來面目，而不存在明確的階段特徵了。如果說這種方法是以地圖中的行（A、B、C、D）來劃分階段的話，那麼它的「狀態轉移」就不全是在兩個階段之間進行的了。
也許這沒什麼大不了的，因為實踐比理論更有說服力。但是，如果我們把題目擴展一下：在地圖中找出從左下角到右上角的兩條路徑，兩條路徑中的任何一條邊都不能重疊，並且要求兩條路徑的總長度最短。這時，再用這種「簡單」的方法就不太好辦了。
如果非得套用這種方法的話，則最優指標函數就需要有四維的下標，並且難以處理兩條路徑「不能重疊」的問題。
而我們回到原先「標准」的動態規劃法，就會發現這個問題很好解決，只需要加一維狀態變數就成了。即用sk=(ak,bk)分別表示兩條路徑走到階段k時所處的位置，相應的，決策變數也增加一維，用uk=(xk,yk)分別表示兩條路徑的行走方向。狀態轉移時將兩條路徑分別考慮：

在寫規劃方程時，只要對兩條路徑走到同一個點的情況稍微處理一下，減少可選的決策個數：

從這個例子中可以總結出設計動態規劃演算法的一個技巧：狀態轉移一般是在相鄰的兩個階段之間（有時也可以在不相鄰的兩個階段間），但是盡量不要在同一個階段內進行。
動態規劃是一種很靈活的解題方法，在動態規劃演算法的設計中，類似的技巧還有很多。要掌握動態規劃的技巧，有兩條途徑：一是要深刻理解動態規劃的本質，這也是我們為什麼一開始就探討它的本質的原因；二是要多實踐，不但要多解題，還要學會從解題中探尋規律，總結技巧。
§3動態規劃與一些演算法的比較
動態規劃作為諸多解題方法中的一種，必然和其他一些演算法有著諸多聯系。從這些聯系中，我們也可以看出動態規劃的一些特點。
§3.1動態規劃與遞推
——動態規劃是最優化演算法
由於動態規劃的「名氣」如此之大，以至於很多人甚至一些資料書上都往往把一種與動態規劃十分相似的演算法，當作是動態規劃。這種演算法就是遞推。實際上，這兩種演算法還是很容易區分的。
按解題的目標來分，信息學試題主要分四類：判定性問題、構造性問題、計數問題和最優化問題。我們在競賽中碰到的大多是最優化問題，而動態規劃正是解決最優化問題的有力武器，因此動態規劃在競賽中的地位日益提高。而遞推法在處理判定性問題和計數問題方面也是一把利器。下面分別就兩個例子，談一下遞推法和動態規劃在這兩個方面的聯系。
[例4] mod 4 最優路徑問題：在下圖中找出從第1點到第4點的一條路徑，要求路徑長度mod 4的余數最小。
這個圖是一個多段圖，而且是一個特殊的多段圖。雖然這個圖的形式比一般的多段圖要簡單，但是這個最優路徑問題卻不能用動態規劃來做。因為一條從第1點到第4點的最優路徑，在它走到第2點、第3點時，路徑長度mod 4的余數不一定是最小，也就是說最優策略的子策略不一定最優——這個問題不滿足最優化原理。
但是我們可以把它轉換成判定性問題，用遞推法來解決。判斷從第1點到第k點的長度mod 4為sk的路徑是否存在，用fk(sk)來表示，則遞推公式如下：
（邊界條件）

（這里lenk,i表示從第k-1點到第k點之間的第i條邊的長度，方括弧表示「或(or)」運算）
最後的結果就是可以使f4(s4)值為真的最小的s4值。
這個遞推法的遞推公式和動態規劃的規劃方程非常相似，我們在這里借用了動態規劃的符號也就是為了更清楚地顯示這一點。其實它們的思想也是非常相像的，可以說是遞推法借用了動態規劃的思想解決了動態規劃不能解決的問題。
有的多階段決策問題（像這一題的階段特徵就很明顯），由於不能滿足最優化原理等使用動態規劃的先決條件，而無法應用動態規劃。在這時可以將最優指標函數的值當作「狀態」放到下標中去，從而變最優化問題為判定性問題，再借用動態規劃的思想，用遞推法來解決問題。
§3.2動態規劃與搜索
——動態規劃是高效率、高消費演算法
同樣是解決最優化問題，有的題目我們採用動態規劃，而有的題目我們則需要用搜索。這其中有沒有什麼規則呢？
我們知道，撇開時空效率的因素不談，在解決最優化問題的演算法中，搜索可以說是「萬能」的。所以動態規劃可以解決的問題，搜索也一定可以解決。
把一個動態規劃演算法改寫成搜索是非常方便的，狀態轉移方程、規劃方程以及邊界條件都可以直接「移植」，所不同的只是求解順序。動態規劃是自底向上的遞推求解，而搜索則是自頂向下的遞歸求解（這里指深度搜索，寬度搜索類似）。
反過來，我們也可以把搜索演算法改寫成動態規劃。狀態空間搜索實際上是對隱式圖中的點進行枚舉，這種枚舉是自頂向下的。如果把枚舉的順序反過來，變成自底向上，那麼就成了動態規劃。（當然這里有個條件，即隱式圖中的點是可排序的，詳見下一節。）
正因為動態規劃和搜索有著求解順序上的不同，這也造成了它們時間效率上的差別。在搜索中，往往會出現下面的情況：
對於上圖(a)這樣幾個狀態構成的一個隱式圖，用搜索演算法就會出現重復，如上圖(b)所示，狀態C2被搜索了兩次。在深度搜索中，這樣的重復會引起以C2為根整個的整個子搜索樹的重復搜索；在寬度搜索中，雖然這樣的重復可以立即被排除，但是其時間代價也是不小的。而動態規劃就沒有這個問題，如上圖(c)所示。
一般說來，動態規劃演算法在時間效率上的優勢是搜索無法比擬的。（當然對於某些題目，根本不會出現狀態的重復，這樣搜索和動態規劃的速度就沒有差別了。）而從理論上講，任何拓撲有序（現實中這個條件常常可以滿足）的隱式圖中的搜索演算法都可以改寫成動態規劃。但事實上，在很多情況下我們仍然不得不採用搜索演算法。那麼，動態規劃演算法在實現上還有什麼障礙嗎？
考慮上圖(a)所示的隱式圖，其中存在兩個從初始狀態無法達到的狀態。在搜索演算法中，這樣的兩個狀態就不被考慮了，如上圖(b)所示。但是動態規劃由於是自底向上求解，所以就無法估計到這一點，因而遍歷了全部的狀態，如上圖(c)所示。
一般說來，動態規劃總要遍歷所有的狀態，而搜索可以排除一些無效狀態。更重要的事搜索還可以剪枝，可能剪去大量不必要的狀態，因此在空間開銷上往往比動態規劃要低很多。
如何協調好動態規劃的高效率與高消費之間的矛盾呢？有一種折衷的辦法就是記憶化演算法。記憶化演算法在求解的時候還是按著自頂向下的順序，但是每求解一個狀態，就將它的解保存下來，以後再次遇到這個狀態的時候，就不必重新求解了。這種方法綜合了搜索和動態規劃兩方面的優點，因而還是很有實用價值的。
§3.3動態規劃與網路流
——動態規劃是易設計易實現演算法
由於圖的關系復雜而無序，一般難以呈現階段特徵（除了特殊的圖如多段圖，或特殊的分段方法如Floyd），因此動態規劃在圖論中的應用不多。但有一類圖，它的點卻是有序的，這就是有向無環圖。
在有向無環圖中，我們可以對點進行拓撲排序，使其體現出有序的特徵，從而據此劃分階段。在有向無還圖中求最短路徑的演算法[4]，已經體現出了簡單的動態規劃思想。但動態規劃在圖論中還有更有價值的應用。下面先看一個例子。
[例6] N個人的街道問題：在街道問題（參見例3）中，若有N個人要從左下角走向右上角，要求他們走過的邊的總長度最大。當然，這里每個人也只能向右或向上走。下面是一個樣例，左圖是從出發地到目的地的三條路徑，右圖是他們所走過的邊，這些邊的總長度為5 + 4 + 3 + 6 + 3 + 3 + 5 + 8 + 8 + 7 + 4 + 5 + 9 + 5 + 3 = 78（不一定是最大）。
這個題目是對街道問題的又一次擴展。仿照街道問題的解題方法，我們仍然可以用動態規劃來解決本題。不過這一次是N個人同時走，狀態變數也就需要用N維來表示，。相應的，決策變數也要變成N維，uk=(uk,1,uk,2,…,uk,N)。狀態轉移方程不需要做什麼改動：

在寫規劃方程時，需要注意在第k階段，N條路徑所走過的邊的總長度的計算，在這里我就用gk(sk,uk)來表示了：

邊界條件為
可見將原來的動態規劃演算法移植到這個問題上來，在理論上還是完全可行的。但是，現在的這個動態規劃演算法的時空復雜度已經是關於N的指數函數，只要N稍微大一點，這個演算法就不可能實現了。
下面我們換一個思路，將N條路徑看成是網路中一個流量為N的流，這樣求解的目標就是使這個流的費用最大。但是本題又不同於一般的費用流問題，在每一條邊e上的流費用並不是流量和邊權的乘積 ，而是用下式計算：

為了使經典的費用流演算法適用於本題，我們需要將模型稍微轉化一下：
如圖，將每條邊拆成兩條。拆開後一條邊上有權，但是容量限制為1；另一條邊沒有容量限制，但是流過這條邊就不能計算費用了。這樣我們就把問題轉化成了一個標準的最大費用固定流問題。
這個演算法可以套用經典的最小費用最大流演算法，在此就不細說了。（參見附錄中的源程序）
這個例題是我仿照IOI97的「障礙物探測器」一題[6]編出來的。「障礙物探測器」比這一題要復雜一些，但是基本思想是相似的。類似的題目還有99年冬令營的「迷宮改造」[7]。從這些題目中都可以看到動態規劃和網路流的聯系。
推廣到一般情況，任何有向無環圖中的費用流問題在理論上說，都可以用動態規劃來解決。對於流量為N（如果流量不固定，這個N需要事先求出來）的費用流問題，用N維的變數sk=(sk,1,sk,2,…,sk,N)來描述狀態，其中sk,iÎV(1£i£N)。相應的，決策也用N維的變數uk=(uk,1,uk,2,…,uk,N)來表示，其中uk,iÎE(sk,i)(1£i£N)，E(v)表示指向v的弧集。則狀態轉移方程可以這樣表示：
sk-1,i = uk,i的弧尾結點
規劃方程為
邊界條件為
但是，由於動態規劃演算法是指數級演算法，因而在實現中的局限性很大，僅可用於一些N非常小的題目。然而在競賽解題中，比如上面說到的IOI97以及99冬令營測試時，我們使用動態規劃的傾向性很明顯（「障礙物探測器」中，我們用的是貪心策略，求N=1或N=2時的局部最優解[8]）。這主要有兩個原因：
一． 雖然網路流有著經典的演算法，但是在競賽中不可能出現經典的問題。如果要運用網路流演算法，則需要經過一番模型轉化，有時這個轉化還是相當困難的。因此在演算法的設計上，靈活巧妙的動態規劃演算法反而要更為簡單一些。
二． 網路流演算法實現起來很繁，這是被人們公認的。因而在競賽的緊張環境中，實現起來有一定模式的動態規劃演算法又多了一層優勢。
正由於動態規劃演算法在設計和實現上的簡便性，所以在N不太大時，也就是在動態規劃可行的情況下，我們還是應該盡量運用動態規劃。
§4結語
本文的內容比較雜，是我幾年來對動態規劃的參悟理解、心得體會。雖然主要的篇幅講的都是理論，但是根本的目的還是指導實踐。
動態規劃，據我認為，是當今信息學競賽中最靈活、也最能體現解題者水平的一類解題方法。本文內容雖多，不能涵蓋動態規劃之萬一。「紙上得來終覺淺，絕知此事要躬行。」要想真正領悟、理解動態規劃的思想，掌握動態規劃的解題技巧，還需要在實踐中不斷地挖掘、探索。實踐得多了，也就能體會到漸入佳境之妙了。
動態規劃，
演算法之常，
運用之妙，
存乎一心。

Ⅱ 數學建模網路流演算法重要嗎你們都用什麼演算法呢

1、蒙特卡羅演算法（該演算法又稱隨機性模擬演算法，是通過計算機模擬來解決問題的演算法，
同時可以通過模擬可以來檢驗自己模型的正確性，是比賽時必用的方法）
2、數據擬合、參數估計、插值等數據處理演算法（比賽中通常會遇到大量的數據需要處理，
而處理數據的關鍵就在於這些演算法，通常使用matlab作為工具）
3、線性規劃、整數規劃、多元規劃、二次規劃等規劃類問題（建模競賽大多數問題屬於最優化問題，
很多時候這些問題可以用數學規劃演算法來描述，通常使用lindo、lingo軟體實現）
4、圖論演算法（這類演算法可以分為很多種，包括最短路、網路流、二分圖等演算法，
涉及到圖論的問題可以用這些方法解決，需要認真准備）
5、動態規劃、回溯搜索、分治演算法、分支定界等計算機演算法（這些演算法是演算法設計中比較常用的方法，很多場合可以用到競賽中）
6、最優化理論的三大非經典演算法：模擬退火法、神經網路、遺傳演算法
（這些問題是用來解決一些較困難的最優化問題的演算法，對於有些問題非常有幫助，
但是演算法的實現比較困難，需慎重使用）
7、網格演算法和窮舉法（網格演算法和窮舉法都是暴力搜索最優點的演算法，在很多競賽題中有應用，
當重點討論模型本身而輕視演算法的時候，可以使用這種暴力方案，最好使用一些高級語言作為編程工具）
8、一些連續離散化方法（很多問題都是實際來的，數據可以是連續的，而計算機只認的是離散的數據，因此將其離散化後進行差分代替微分、求和代替積分等思想是非常重要的）
9、數值分析演算法（如果在比賽中採用高級語言進行編程的話，那一些數值分析中常用的演算法比
如方程組求解、矩陣運算、函數積分等演算法就需要額外編寫庫函數進行調用）
10、圖象處理演算法（賽題中有一類問題與圖形有關，即使與圖形無關，論文中也應該要不乏圖片的，
這些圖形如何展示以及如何處理就是需要解決的問題，通常使用matlab進行處理）

Ⅲ 一個網路流演算法題

將原樹樹鏈剖分後建線段樹。

對於每個旅行商從原點向旅行商連ci,旅行商向線段樹對應區間連無窮。
城市向匯點連wi
最大流即可

Ⅳ 程序員必須掌握哪些演算法

一.基本演算法:

枚舉. (poj1753,poj2965)

貪心(poj1328,poj2109,poj2586)

遞歸和分治法.

遞推.

構造法.(poj3295)

模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.圖演算法:

圖的深度優先遍歷和廣度優先遍歷.

最短路徑演算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
最小生成樹演算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
拓撲排序 (poj1094)

二分圖的最大匹配 (匈牙利演算法) (poj3041,poj3020)

最大流的增廣路演算法(KM演算法). (poj1459,poj3436)

三.數據結構.

串 (poj1035,poj3080,poj1936)

排序(快排、歸並排(與逆序數有關)、堆排) (poj2388,poj2299)

簡單並查集的應用.

哈希表和二分查找等高效查找法(數的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
哈夫曼樹(poj3253)

堆

trie樹(靜態建樹、動態建樹) (poj2513)

四.簡單搜索

深度優先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)

廣度優先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)

簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)

五.動態規劃

背包問題. (poj1837,poj1276)

型如下表的簡單DP(可參考lrj的書 page149):
E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列) (poj3176,poj1080,poj1159)
C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)
六.數學

組合數學:
1.加法原理和乘法原理.
2.排列組合.
3.遞推關系.
(POJ3252,poj1850,poj1019,poj1942)
數論.
1.素數與整除問題
2.進制位.
3.同餘模運算.
(poj2635, poj3292,poj1845,poj2115)
計算方法.
1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)
七.計算幾何學.

幾何公式.

叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)

多邊型的簡單演算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)
(poj1408,poj1584)
凸包. (poj2187,poj1113)

中級（校賽壓軸及省賽中等難度）:
一.基本演算法:

C++的標准模版庫的應用. (poj3096,poj3007)

較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)

二.圖演算法:

差分約束系統的建立和求解. (poj1201,poj2983)

最小費用最大流(poj2516,poj2516,poj2195)

雙連通分量(poj2942)

強連通分支及其縮點.(poj2186)

圖的割邊和割點(poj3352)

最小割模型、網路流規約(poj3308)

三.數據結構.

線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)

靜態二叉檢索樹. (poj2482,poj2352)

樹狀樹組(poj1195,poj3321)

RMQ. (poj3264,poj3368)

並查集的高級應用. (poj1703,2492)

KMP演算法. (poj1961,poj2406)

四.搜索

最優化剪枝和可行性剪枝

搜索的技巧和優化 (poj3411,poj1724)

記憶化搜索(poj3373,poj1691)

五.動態規劃

較為復雜的動態規劃(如動態規劃解特別的旅行商TSP問題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
記錄狀態的動態規劃. (POJ3254,poj2411,poj1185)

樹型動態規劃(poj2057,poj1947,poj2486,poj3140)

六.數學

組合數學:
1.容斥原理.
2.抽屜原理.
3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).
4.遞推關系和母函數.
數學.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率問題. (poj3071,poj3440)
3.GCD、擴展的歐幾里德(中國剩餘定理) (poj3101)
計算方法.
1.0/1分數規劃. (poj2976)
2.三分法求解單峰(單谷)的極值.
3.矩陣法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
隨機化演算法(poj3318,poj2454)
雜題(poj1870,poj3296,poj3286,poj1095)
七.計算幾何學.

坐標離散化.

掃描線演算法(例如求矩形的面積和周長並,常和線段樹或堆一起使用)
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
多邊形的內核(半平面交)(poj3130,poj3335)

幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高級（regional中等難度）:
一.基本演算法要求:

代碼快速寫成,精簡但不失風格

(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)

保證正確性和高效性. poj3434

二.圖演算法:

度限制最小生成樹和第K最短路. (poj1639)

最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
最優比率生成樹. (poj2728)

最小樹形圖(poj3164)

次小生成樹.

無向圖、有向圖的最小環

三.數據結構.

trie圖的建立和應用. (poj2778)

LCA和RMQ問題(LCA(最近公共祖先問題) 有離線演算法(並查集+dfs) 和 在線演算法(RMQ+dfs)).(poj1330)
雙端隊列和它的應用(維護一個單調的隊列,常常在動態規劃中起到優化狀態轉移的目的). (poj2823)
左偏樹(可合並堆).

後綴樹(非常有用的數據結構,也是賽區考題的熱點).(poj3415,poj3294)
四.搜索

較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

廣搜的狀態優化:利用M進制數存儲狀態、轉化為串用hash表判重、按位壓縮存儲狀態、雙向廣搜、A*演算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)

深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*演算法. (poj3131,poj2870,poj2286)

五.動態規劃

需要用數據結構優化的動態規劃.(poj2754,poj3378,poj3017)
四邊形不等式理論.

較難的狀態DP(poj3133)

六.數學

組合數學.
1.MoBius反演(poj2888,poj2154)
2.偏序關系理論.
博奕論.
1.極大極小過程(poj3317,poj1085)
2.Nim問題.
七.計算幾何學.

半平面求交(poj3384,poj2540)

可視圖的建立(poj2966)

點集最小圓覆蓋.

對踵點(poj2079)

Ⅳ 網路流的資料

編輯本段定義
圖論中的一種理論與方法，研究網路上的一類最優化問題 。1955年 ，T.E. 哈里斯在研究鐵路最大通量時首先提出在一個給定的網路上尋求兩點間最大運輸量的問題。1956年，L.R. 福特和 D.R. 富爾克森等人給出了解決這類問題的演算法，從而建立了網路流理論。所謂網路或容量網路指的是一個連通的賦權有向圖 D＝ （V、E、C） ， 其中V 是該圖的頂點集，E是有向邊(即弧)集，C是弧上的容量。此外頂點集中包括一個起點和一個終點。網路上的流就是由起點流向終點的可行流，這是定義在網路上的非負函數，它一方面受到容量的限制，另一方面除去起點和終點以外，在所有中途點要求保持流入量和流出量是平衡的。如果把下圖看作一個公路網，頂點v1…v6表示6座城鎮，每條邊上的權數表示兩城鎮間的公路長度。現在要問 ：若從起點v1將物資運送到終點v6去 ，應選擇那條路線才能使總運輸距離最短�這樣一類問題稱為最短路問題 。 如果把上圖看作一個輸油管道網 ， v1 表示發送點，v6表示接收點，其他點表示中轉站 ，各邊的權數表示該段管道的最大輸送量。現在要問怎樣安排輸油線路才能使從v1到v6的總運輸量為最大。這樣的問題稱為最大流問題。
最大流理論是由福特和富爾克森於 1956 年創立的 ，他們指出最大流的流值等於最小割(截集)的容量這個重要的事實，並根據這一原理設計了用標號法求最大流的方法，後來又有人加以改進，使得求解最大流的方法更加豐富和完善 。最大流問題的研究密切了圖論和運籌學，特別是與線性規劃的聯系，開辟了圖論應用的新途徑。
目前網路流的理論和應用在不斷發展，出現了具有增益的流、多終端流、多商品流以及網路流的分解與合成等新課題。網路流的應用已遍及通訊、運輸、電力、工程規劃、任務分派、設備更新以及計算機輔助設計等眾多領域。

網路流演算法
一、網路流的基本概念
先來看一個實例。
現在想將一些物資從S運抵T，必須經過一些中轉站。連接中轉站的是公路，每條公路都有最大運載量。如下圖：
每條弧代表一條公路，弧上的數表示該公路的最大運載量。最多能將多少貨物從S運抵T？
這是一個典型的網路流模型。為了解答此題，我們先了解網路流的有關定義和概念。
若有向圖G=(V,E)滿足下列條件：
1、 有且僅有一個頂點S，它的入度為零，即d-(S) = 0，這個頂點S便稱為源點，或稱為發點。
2、 有且僅有一個頂點T，它的出度為零，即d+(T) = 0，這個頂點T便稱為匯點，或稱為收點。
3、 每一條弧都有非負數，叫做該邊的容量。邊(vi, vj)的容量用cij表示。
則稱之為網路流圖，記為G = (V, E, C)
譬如圖5-1就是一個網路流圖。
1．可行流
對於網路流圖G，每一條弧(i,j)都給定一個非負數fij，這一組數滿足下列三條件時稱為這網路的可行流，用f表示它。
1、 每一條弧(i,j)有fij≤cij。
2、 除源點S和匯點T以外的所有的點vi，恆有：
該等式說明中間點vi的流量守恆，輸入與輸出量相等。
3、 對於源點S和匯點T有：
這里V(f)表示該可行流f的流量。
例如對圖5-1而言，它的一個可行流如下：
流量V(f) = 5。
2．可改進路
給定一個可行流f=。若fij = cij，稱<vi, vj>為飽和弧；否則稱<vi, vj>為非飽和弧。若fij = 0，稱<vi, vj>為零流弧；否則稱<vi, vj>為非零流弧。
定義一條道路P，起點是S、終點是T。把P上所有與P方向一致的弧定義為正向弧，正向弧的全體記為P+；把P上所有與P方向相悖的弧定義為反向弧，反向弧的全體記為P-。
譬如在圖5-1中，P = (S, V1, V2, V3, V4, T)，那麼
P+ = {<S, V1>, <V1, V2>, <V2, V3>, <V4, T>}
P- = {<V4, V3>}
給定一個可行流f，P是從S到T的一條道路，如果滿足：
那麼就稱P是f的一條可改進路。（有些書上又稱：可增廣軌）之所以稱作「可改進」，是因為可改進路上弧的流量通過一定的規則修改，可以令整個流量放大。具體方法下一節會重點介紹，此不贅述。
3．割切
要解決網路最大流問題，必須先學習割切的概念和有關知識。
G = (V, E, C)是已知的網路流圖，設U是V的一個子集，W = V\U，滿足S U，T W。即U、W把V分成兩個不相交的集合，且源點和匯點分屬不同的集合。
對於弧尾在U，弧頭在W的弧所構成的集合稱之為割切，用（U，W）表示。把割切（U，W）中所有弧的容量之和叫做此割切的容量，記為C（U，W），即：
例如圖5-1中，令U = {S, V1}，則W = {V2, V3, V4, T}，那麼
C(U, W) = <S, V2> + <V1, V2> + <V1, V3>+<V1, V4>=8+4+4+1=17
定理：對於已知的網路流圖，設任意一可行流為f，任意一割切為(U, W)，必有：V(f) ≤ C(U, W)。
通俗簡明的講：「最大流小於等於最小割」。這是「流理論」里最基礎最重要的定理。整個「流」的理論系統都是在這個定理上建立起來的，必須特別重視。
下面我們給出證明。
網路流、可改進路、割切都是基礎的概念，應該扎實掌握。它們三者之間乍一看似乎風馬牛不相干，其實內在聯系是十分緊密的。
二、求最大流
何謂最大流？首先它必須是一個可行流；其次，它的流量必須達到最大。這樣的流就稱為最大流。譬如對圖5-1而言，它的最大流如下：
下面探討如何求得最大流。
在定義「可改進路」概念時，提到可以通過一定規則修改「可改進路」上弧的流量，可以使得總流量放大。下面我們就具體看一看是什麼「規則」。
對可改進路P上的弧<vi, vj>，分為兩種情況討論：
第一種情況：<vi, vj>∈P+，可以令fij增加一個常數delta。必須滿足fij + delta ≤ cij，即delta ≤ cij – fij。
第二種情況：<vi, vj>∈P-，可以令fij減少一個常數delta。必須滿足fij - delta ≥ 0，即delta ≤ fij
根據以上分析可以得出delta的計算公式：
因為P+的每條弧都是非飽和弧，P-的每條弧都是非零流弧，所以delta > 0。
容易證明，按照如此規則修正流量，既可以使所有中間點都滿足「流量守恆」（即輸入量等於輸出量），又可以使得總的流量有所增加（因為delta > 0）。
因此我們對於任意的可行流f，只要在f中能找到可改進路，那麼必然可以將f改造成為流量更大的一個可行流。我們要求的是最大流，現在的問題是：倘若在f中找不到可改進路，是不是f就一定是最大流呢？
答案是肯定的。下面我們給出證明。
定理1 可行流f是最大流的充分必要條件是：f中不存在可改進路。
證明：
首先證明必要性：已知最大流f，求證f中不存在可改進路。
若最大流f中存在可改進路P，那麼可以根據一定規則（詳見上文）修改P中弧的流量。可以將f的流量放大，這與f是最大流矛盾。故必要性得證。
再證明充分性：已知流f，並且f中不存在可改進路，求證f是最大流。
我們定義頂點集合U, W如下：
（a） S∈U，
（b） 若x∈U，且fxy<cxy，則y∈U;
若x∈U，且fyx>0，則y∈U。
（這實際上就是可改進路的構造規則）
（c） W = V \ U。
由於f中不存在可改進路，所以T∈W；又S∈U，所以U、W是一個割切（U, W）。
按照U的定義，若x∈U，y∈W，則fxy = cxy。若x∈W，y∈U，則fxy = 0。
所以，
又因 v(f)≤C(U,W)
所以f是最大流。得證。
根據充分性證明中的有關結論，我們可以得到另外一條重要定理：
最大流最小割定理：最大流等於最小割，即max V(f) = min C(U, W)。
至此，我們可以輕松設計出求最大流的演算法：
step 1. 令所有弧的流量為0，從而構造一個流量為0的可行流f（稱作零流）。
step 2. 若f中找不到可改進路則轉step 5；否則找到任意一條可改進路P。
step 3. 根據P求delta。
step 4. 以delta為改進量，更新可行流f。轉step 2。
step 5. 演算法結束。此時的f即為最大流。
三、最小費用最大流
1．問題的模型
流最重要的應用是盡可能多的分流物資，這也就是我們已經研究過的最大流問題。然而實際生活中，最大配置方案肯定不止一種，一旦有了選擇的餘地，費用的因素就自然參與到決策中來。
圖5-8是一個最簡單的例子：弧上標的兩個數字第一個是容量，第二個是費用。這里的費用是單位流量的花費，譬如fs1=4，所需花費為3*4=12。
容易看出，此圖的最大流（流量是8）為：fs1 = f1t = 5, fs2 = f2t = 3。所以它的費用是：3*5+4*5+7*3+2*3 = 62。
一般的，設有帶費用的網路流圖G = (V, E, C, W)，每條弧<Vi, Vj>對應兩個非負整數Cij、Wij，表示該弧的容量和費用。若流f滿足：
(a) 流量V(f)最大。
(b) 滿足a的前提下，流的費用Cost(f) = 最小。
就稱f是網路流圖G的最小費用最大流。
2．演算法設計
我們模仿求最大流的演算法，找可改進路來求最小費用最大流。
設P是流f的可改進路，定義 為P的費用（為什麼如此定義？）。如果P是關於f的可改進路中費用最小的，就稱P是f的最小費用可改進路。
求最小費用最大流的基本思想是貪心法。即：對於流f，每次選擇最小費用可改進路進行改進，直到不存在可改進路為止。這樣的得到的最大流必然是費用最小的。
演算法可描述為：
step 1. 令f為零流。
step 2. 若無可改進路，轉step 5；否則找到最小費用可改進路，設為P。
step 3. 根據P求delta（改進量）。
step 4. 放大f。轉step 2。
step 5. 演算法結束。此時的f即最小費用最大流。
至於演算法的正確性，可以從理論上證明。讀者可自己思考或查閱有關運籌學資料。
2．最小費用可改進路的求解
求「最小費用可改進路」是求最小費用最大流演算法的關鍵之所在，下面我們探討求解的方法。
設帶費用的網路流圖G = (V, E, C, W)，它的一個可行流是f。我們構造帶權有向圖B = (V』, E』)，其中：
1、 V』 = V。
2、 若<Vi, Vj>∈E，fij<Cij，那麼<Vi, Vj>∈E』，權為Wij。
若<Vi, Vj>∈E，fij>0，那麼<Vj, Vi>∈E』，權為-Wij。
顯然，B中從S到T的每一條道路都對應關於f的一條可改進路；反之，關於f的每條可改進路也能對應B中從S到T的一條路徑。即兩者存在一一映射的邏輯關系。
故若B中不存在從S到T的路徑，則f必然沒有可改進路；不然，B中從S到T的最短路徑即為f的最小費用可改進路。
現在的問題變成：給定帶權有向圖B = (V』, E』)，求從S到T的一條最短路徑。
考慮到圖中存在權值為負數的弧，不能採用Dijkstra演算法；Floyd演算法的效率又不盡如人意——所以，這里採用一種折衷的演算法：迭代法。
設Short[k]表示從S到k頂點的最短路徑長度；從S到頂點k的最短路徑中，頂點k的前趨記為Last[k]。那麼迭代演算法描述如下：（為了便於描述，令n = |V』|，S的編號為0，T的編號為n+1）
step 1. 令Short[k]  +∞（1≤k≤n+1），Short[0]  0。
step 2. 遍歷每一條弧<Vk, Vj>。若Short[k] + <k, j> < Short[j]，則令Short[j]  Short[k] + <k, j>，同時Last[j]  k。倘不存在任何一條弧滿足此條件則轉step 4。
step 3. 轉step 2.
step 4. 演算法結束。若Short[n + 1]= +∞，則不存在從S到T的路徑；否則可以根據Last記錄的有關信息得到最短路徑。
一次迭代演算法的時間復雜度為O(kn2)，其中k是一個不大於n的變數。在費用流的求解過程中，k大部分情況下都遠小於n。
3．思維發散與探索
1）可改進路費用：「遞增！遞增？」
設f從零流到最大流共被改進了k次，每i次選擇的可改進路的費用為pi，那麼會不會有p1≤p2≤p3≤……≤pk呢？
2）迭代法：「小心死循環！嘿嘿……」
迭代法會出現死循環嗎？也就是說，構造的帶權有向圖B中會存在負迴路嗎？
3）費用：「你在乎我是負數嗎？」
網路流圖中的費用可以小於零嗎？
4）容量：「我管的可不僅是弧。」
網路流圖中的「容量」都是對弧而言的，但若是給每個頂點也加上一個容量限制：即通過此頂點的流量的上限；任務仍然是求從S到T的最小費用最大流。你能解決嗎？
四、有上下界的最大流
上面討論的網路流都只對每條弧都限定了上界（其實其下界可以看成0），現在給每條弧<Vi, Vj>加上一個下界限制Aij（即必須滿足Aij≤fij）。
例如圖5-9：
弧上數字對第一個是上界，第二個是下界。若是撇開下界不看，此圖的最大流如圖5-10(a)所示，流量是6；但若是加入了下界的限制，它的最大流量就只有5了，具體方案見圖5-10(b)。
那麼有上下界的網路最大流怎麼求呢？
一種自然的想法是去掉下界，將其轉化為只含上界的網路流圖。這種美好的願望是可以實現的。具體方法如下：
設原網路流圖為G = (V, E, C, A)，構造不含下界的網路流圖G』 = (V』, E』, C』)：
1、 V』 = V∪{S』, T』}
2、 對每個頂點x，令 ，若h-(x)≠0，就添加一條弧<S』, x>，其上界為h-(x)。
3、 對每個頂點x，令 ，若h+(x)≠0，就添加一條弧<x, T』>，其上界為h+(x)。
4、 對於任何<Vi, Vj>∈E，都有<Vi, Vj>∈E』，其上界C』ij = Cij – Aij。
5、 新增<T, S>∈E』，其上界CTS = +∞。
在G』中以S』為源點、T』為匯點求得最大流f』。若f』中從S』發出的任意一條弧是非飽和弧，則原網路流圖沒有可行流。否則可得原圖的一個可行流f = f』 + A，即所有的fij = f』ij + Aij。（其正確性很容易證明，留給讀者完成）
然後再求可改進路（反向弧<Vi, Vj>必須滿足fij≥Aij，而非fij≥0），不斷放大f，直到求出最大流。
我們看到，上幾節所討論的一種可行網路流實際上是{Aij = 0}的一種特殊網路流，這里提出的模型更一般化了。解決一般化的復雜問題，我們採取的思路是將其轉化為特殊的簡單問題，加以研究、推廣，進而解決。這是一種重要的基本思想：化歸——簡單有效。基於這種思想，請讀者自行思考解決：
1、 有上下界的最小流。
2、 有上下界的最小費用最大流。
五、多源點、多匯點的最大流
已知網路流圖有n個源點S1、S2、……、Sn，m個匯點T1、T2、……、Tm，，求該圖的最大流。這樣的問題稱為多源點、多匯點最大流。
它的解決很簡單：
1、 增設一個「超級源」S』，對每個源點Si，新增弧<S』, Si>，容量為無窮大。
2、 增設一個「超級匯」T』，對每個匯點Ti，新增弧<Ti, T』>，容量為無窮大。
3、 以S』為源點、T』為匯點求最大流f。
4、 將f中的S』和T』去掉，即為原圖的最大流。
演算法正確性顯然。
六、頂點有容量限制的最大流
上一節已經提出了這個問題，即對於進出每個頂點的流量也規定一個上限，這樣的最大流如何求？
既然我們已經解決了「邊限制」問題，現在何不把「點限制」問題轉化為「邊限制」呢？具體辦法如下：
1、 對除源點和匯點之外的每個頂點i拆分成兩個頂點i』和i』』。新增一條弧<i』, i』』>，其容量為點i的流量限制。
2、 對於原圖中的弧<i, j>，我們將其變換成<i』』, j』>。
3、 對變換後的圖求最大流即可。
這里我們又一次運用到了化歸的思想：將未知的「點限制」問題轉化為已知的「邊限制」問題。
七、網路流與二部圖的匹配
{二部圖和匹配的定義可參見本書專門介紹二部圖匹配的章節}
設二部圖為G = (X, Y, E)。
增設點S』，對於所有i∈X，新增弧<S』, Xi>，容量為1；增設點T』，對於所有i∈Y，新增一條弧<Yi, T』>，容量也為1。原圖中所有的弧予以保留，容量均為+∞。對新構造出來的網路流圖以S』為源點、T』為匯點求最大流：流量即為最大匹配數；若弧<Xi, Yj>（i∈X，j∈Y）的流量非零，它就是一條匹配邊。
二部圖最大匹配問題解決。
那麼二部圖的最佳匹配問題又如何？
仍然按照上述方法構圖。同時令原圖中弧的費用保持不變；新增弧的費用置為0。然後以S』為源點、T』為匯點求最小費用最大流即可。最大流的費用即為原二部圖最佳匹配的費用。

復制的我快吐了~