最大流在信息學競賽中應用的一個模型-江濤

1、NOI2006年冬令營講座最大流在信息學競賽中應用的一個模型江濤關鍵字：網(wǎng)絡 可行流 最大流 附加網(wǎng)絡無源匯引言：必要孤流的分離有上下界的最大流 建模最大流類的模型在當今信息學比賽中有相當廣泛的應 用。但在教學中，發(fā)現(xiàn)很多同學對流模型的原理和變形并不 掌握，只是記下經(jīng)典的算法和題目，以便比賽中套用。這當然有很大的局限性，也不是學習之正道。本講想通 過對最大流模型，特別是附加網(wǎng)絡的一些分析、討論，達到 拋磚引玉目的。一個實例：運輸網(wǎng)絡圖1.1網(wǎng)絡定義： 一個有向圖G=(V, E)；有兩個特別的點：源點s、匯點t；圖中每條邊(u,v)EE，有一個非負值的容量C(u,v)記為 G=(V, E, C)

2、網(wǎng)絡三要素：點、邊、容量可行流定義：是網(wǎng)絡G上的一個“流”，即每條邊上有個“流量”P(u,v), 要滿足下面兩個條件：流的容量限制-弧：0 J P(u, W J C(u, V)對任意弧(u,v)有 向邊流的平衡-點：除源點和匯點，對任意中間點有：流入u的“流量”與流出u的“流量”相等。即：Vu e V - s, t有2 P (X, u)-2 P (u, x) = 0 xeVxeV網(wǎng)絡的流量：源點的凈流出“流量”或 匯點的凈流入“流量”。即： P (s, X)- P 3, s) = P 3, t)- P (t, X)xeVxeVxeVxeV注意，我們這里說的流量是一種速率，而不是指總量。聯(lián)系上面

3、所說的實例，下面是一個流量為1的可行流：圖1.2標準圖示法:圖1.3例1.1有一個n*m的國際棋盤，上面有一些格子被挖掉， 即不能放棋子，現(xiàn)求最多能放多少個棋子“車”，并保證它 們不互相攻擊（即：不在同一行，也不在同一列）？分析：1）行、列限制-最多只能一個車控制；2）車對行、列的影響-一個車控制一個行和邊；圖1.4圖1.5顯然，我們要求車最多，也就是求流量最大- 下面是一個解：-最大流問題。圖1.6即（1,3）、（2,1）、（3,2）格上各放一個車，可得到一個最優(yōu)方案。二、最大流問題尋找網(wǎng)絡G上可能的最大流量（和一個有最大流量的可行 流方案），即為網(wǎng)絡G上的最大流問題。我們再來看看圖1.1的

4、運輸網(wǎng)絡例子，我們可能通過改進 圖1.3得到下面這樣的可行流：圖2.1求解過程中的困惑：問題2.1流量還可能增加嗎？問題22如果能增加，怎樣改進?三、最大流算法的核心一增廣路徑退流的概念一后向弧仔細分析圖2.1，我們發(fā)現(xiàn)，流量是可以增加的:圖3.1把一個流量弧(B,C)和(C,T)上的流退回到B圖3.2圖3.1不能“直接尋找增大流的路徑是因為當初有些弧上的流 選擇不“恰當”要“退流”一種直觀的想法就是：調(diào)整或重新搜索“當初的選擇”- 難！能不能保留以前的工作，而在這之上改進呢？經(jīng)過專家 們研究發(fā)現(xiàn)，加入退流思想-后向弧，就能再次“直接尋找 增大流的路徑”。增廣路徑（可改進路徑）的定義匹1=1若

5、P是網(wǎng)絡中連結源點s和匯點t的一條路，我們定義路的方向是從s到t，則路上的弧有兩種：前向弧-弧的方向與路的方向一致。前向弧的全體記為P+；后向弧-弧的方向與路的方向相反。后向弧的全體記為P-；設F是一個可行流，P是從s到t的一條路，若P滿足 下列條件：在P+的所有前向弧(u,v)上，0Mf(u,v) C(u,v);在P-的所有后向弧(u,v)上，0f(u,v) MC(u,v);則稱P是關于可行流F的一條可增廣路徑。圖3.3本圖中:S-A-C-B-D-E-T為一增廣路徑。其中(C,B)為后向弧， 其它為前向弧。在增廣路徑上的改進算法:匹1=1求路徑可改進量；C (P) = min前向弧C(u,v

6、)- f(u,v)、后向弧f(v,u) f(u ,v )eP修改增廣路徑上的流量；四、附加網(wǎng)絡1-殘留網(wǎng)絡由于要考慮前向弧、后向弧，分析、描述時不簡潔，在 圖2.1上直觀看也不容易看出增廣路徑。因此我們把已經(jīng)有的流量從容量中分離出來表示，引入 一個與原問題等價的附加網(wǎng)絡1：殘留網(wǎng)絡。圖4.1其中，前向?。ê谏┥系娜萘繛椤笆Ｓ嗳萘俊?C（u,v）-f（u,v）； 后向?。t色）上的容量為“可退流量” =f（v，u）。改造后的網(wǎng)如下:圖4.2在這張圖上，我們找增廣路徑顯的非常直觀了 !結合增廣路徑，我們有如下定理：最大流定理如果殘留網(wǎng)絡上找不到增廣路徑，則當前流為最大流;匹1=1反之，如果當前流

7、不為最大流，則定有增廣路徑。匹1=1證明涉及最小割概念，不是本文重點，由于時間關系，從 略。至此，問題2.1和問題2.2在這個最大流定理中同時獲得解 決。求最大流的基本思想：初始化一個可行流：f (u, v) 0 對所有u,v e V現(xiàn)有網(wǎng)絡流的殘留網(wǎng)絡上有增廣路徑嗎？Yn按上面方法對增廣路徑改進f為最大流基于這種思想的算法，關鍵之處在于怎樣找增廣路徑。常用方法有：深度搜索dfs寬度搜索bfs優(yōu)先搜索pfs-即類似Dijkstra算法的標號法。另外，求最小費用最大流問題（每條邊有個費用），只要把 每次“找增廣路徑”改為“找費用最小的增廣路徑”即可。（證明從略）五、小結一前面幾小節(jié)，回顧了最大流

8、算法的一些基本概念和原 理，特別提到了把已有流量分離出來單獨表示的方法：殘留 網(wǎng)絡。這個與原問題等價的附加網(wǎng)絡使問題的描述、思考方 便簡潔而統(tǒng)一。注意這幾個關鍵詞：流分離單獨表示等價方便簡潔它們表達了一種思路，一種分析、表示最大流問題的方法。前幾年的國家集訓隊有幾篇關于最大流的論文，作者關 注的就是分析問題時怎樣建立數(shù)學模型。如廣東北江中學的李偉星在論文最大流的摘要中說:“許多問題可以先轉(zhuǎn)化為網(wǎng)絡流問題，再運用最大流算 法加以解決。而發(fā)現(xiàn)問題本質(zhì)，根據(jù)最大流算法的特點，設 計與之相配的數(shù)學模型是運用最大流算法解決問題的重要步驟。”福建師大附中的江鵬同學在論文從一道題目的解法試 談網(wǎng)絡流的構造與

9、算法的引論中也有這樣一句話：“網(wǎng)絡流在具體問題中的應用，最具挑戰(zhàn)性的部分是 模型的構造。這沒用現(xiàn)成的模式可以套用，需要對各種網(wǎng) 絡流的性質(zhì)了如指掌(比如點有容量、容量有上下限、多 重邊等等)，并且歸納總結一些經(jīng)驗，發(fā)揮我們的創(chuàng)造性?！笔堑模谛畔W競賽中很多最大流相關問題沒有現(xiàn)成模 式可以套用，但解決最大流問題的原理和思想是相通的，前 面所說的構造等價的附加網(wǎng)絡的思路和方法就是一種可以 借用的“現(xiàn)成模式”。為了進一步的討論，先看一個更復雜的問題：例題5.1變形一筆畫問題在一個有向圖，判斷能不能一筆畫訪問所有的邊，但有 些弧上可以畫多次。我們用容量C(u,v)表示弧(u,v)最多可以 重復畫的次

10、數(shù)。分析：由于除了開始點和結束點，每個點進入次數(shù)與離開次數(shù)是相同的。因此滿足流平衡條件，可以想到用流模型做。但 這里每條弧都要畫到，即最少要畫一次。因此，成為有上下 界的流問題。這種流的容量有上下界時求解的問題，在信息學比賽中 也很常見。下面將對這類問題做進一步討論，我們會發(fā)現(xiàn)， 運用“流分離、構造等價附加網(wǎng)”的思想，解決的難度并不 比前面最大流問題大。六、附加網(wǎng)絡2無源匯的可行流如果每個點都考慮流的平衡，而沒有了源點s和匯點t， 則我們稱為無源匯的可行流。有一種簡單的方法可以將普通的網(wǎng)絡上的可行流要改 成無源匯的可行流：加一條邊(t,s)，容量為可根據(jù)需要設定為+8或其它值.例11的這種改變

11、如下：_圖6.1例題5.8圖6.2注：我們用弧上的a,b數(shù)對表示容量的上下界。無源匯的可行流問題(特指有上下界的流網(wǎng)絡)：在一個有上下界的流網(wǎng)絡G中，不設源和匯，但要求任 意一個點i都滿足流量平衡條件： f (u,i) = f (i, v)(u ,i )eE(i ,v )eE且每條邊(u, v)都滿足容量限制B(u, v)f(u, v)C(u, v)的 條件下，尋找一個可行流f,或指出這樣的可行流不存在。 不妨稱這個問題為無源匯的可行流。-參見周源的一種簡易的方法求解流量有上下界的網(wǎng)絡中網(wǎng)絡流問題上圖中把源、匯連接起來了，沒有了源和匯，怎么求其 上的可行流呢？是的，沒有了源、匯，以前的最大流算

12、法就成了無的之 矢，一定要有源和匯。那我們?yōu)槭裁催€要把有源、匯的問題 改成無源、匯呢？答案是破舊立新：沒了舊的源、匯，我們可以更加自由地按需要設立新的 源、匯。從而使網(wǎng)絡模型變成一個新的附加網(wǎng)絡！七、附加網(wǎng)絡3-必要性流的分離對于有上下界的最大流網(wǎng)絡流問題，我們可以看成是在 滿足“必要”的下界情況時，求最大流（或最小費用等問題）。 直觀的一種思路就是：求一個滿足下界的流fl;在fl基礎上用尋找增廣路徑的方法，擴大流，直到?jīng)]有 增廣路徑；實現(xiàn)的關鍵點在于：問題7.1：怎樣求滿足下界而又不超過上界的一個流fl？問題7.2:怎樣增大流fl，而又同時不破壞下界？總體上看，下界是一條弧必需要滿足的確定值

13、，我們能 不能把這個下界“分離”出去，從而使問題轉(zhuǎn)為下界為0， 也就是普通的最大流問題的可行流問題？先用一個類似的實例來分析說明：例題7.1:N個石子，分成M堆，要求第i堆的石子數(shù)大于給定的 正整數(shù)q，問有多少種方法？轉(zhuǎn)化問題：N= N 一 C個石子，要求分成m堆，問有多少I種排列方法?圖7.1圖7.2組合數(shù)學問題：一列N個1中間有N，-個可分隔點，選M-1個，把1 分成M段，有多少方法？圖7.3結果:C(N - 1,M - 1)類似地，我們設法運用流分離的思想，找一個等價的附 加網(wǎng)絡3,使問題7.1和問題7.2得到方便而統(tǒng)一地解決。（一）觀察一條路徑情況2,63,43,7圖7.4如同例7.1

14、直接把容量下界減掉怎樣?圖7.5顯然，如果圖7.5中的流想通過加上下界來對應地得到 圖7.4中的解是不可能的。因此，這里流的分離不能用簡單 減掉的方法，而應該把一個弧分離成兩個弧。即加一個容量 等于下界的必要弧，使可行流分離在這兩個弧上。如下圖：414233圖7.6一個無源匯的可行流的方案一定是必要弧是滿的。因此 現(xiàn)在我們先要找一個把必要弧充滿的可行流（當然也要滿足 上界限制）?，F(xiàn)在我們的目光焦點是必要弧，把他們集中起來：414圖7.7由于必要弧都是要飽和的，顯然與下面圖是等價的。41圖7.8進一步，加弧(T,S)，容量不限，成無源匯可行流問題。 再去除X,Y之間的連線，使Y、X分別成為新的源

15、和匯。+ 8圖7.9如果Y到X的最大流能為2+3+3，則顯然有:必要弧為滿滿足容量上界限制保持流平衡(二)網(wǎng)絡整體情況再來看看例5.1，先分離必要弧:圖 7.10改造：由于可行流的源S流出與匯T流出應該是相等的，31加條邊(T,S)，容量+8。割開所有必要弧，加兩個附加源Y 和匯X：圖 7.11至此：問題成功轉(zhuǎn)化為求Y到X的普通最大流問題。我 們稱這個改造后的網(wǎng)絡模型為附加圖絡3?；仡櫛竟?jié)我們要解決的問題：問題7.1：怎樣求滿足下界而又不超過上界的一個流fl?問題7.2:怎樣增大流門，而又同時不破壞下界？當求出附加網(wǎng)絡3的最大流為1+1+1+1+1=5時，我們再 反過來做：把“進X”和“出Y”

16、的對應邊連上，則找到一 個有上下界容量限制和無源匯可行流。再把?。ǎ┠米?，則 問題7.1解決。1/+8圖 7.12注意：原問題可行流存在無解情況，即附加網(wǎng)絡3的最大流 不能把源（或匯）相連的弧飽和。不同于普通最大流：因下界 為0時，一定有解。在得到一個可行流f1之后，現(xiàn)在我們再來看看問題7.2。再去掉邊(T,S)-上圖即為弧(5,1),還原成有源匯最大流 的原問題。如果要求這時的最大流，則可在這個基礎上，找增廣路 徑來增大流，最終求得一個符合要求的最大流方案。但是要注意的是，對必要弧，我們不能退流，因此相應的殘留網(wǎng)絡對必要弧要單獨處理，或直接暫時拿走，再做附加網(wǎng)絡2,如果對上例處理，則:1/

17、1圖 7.13圖 7.14當然，本例不可能再增大流了例子僅對解決問題7.2的圖示說明。另外，這種情況下的增廣路徑改進，不會影響必要弧-即: 不破壞下界。八、小結二求容量有上下界最大流的基本思想:競賽中的實用算法：周源同學在IOI2004國家集訓隊作業(yè)一種簡易的方法求 解流量有上下界的網(wǎng)絡中網(wǎng)絡流問題，是對上面方法的簡 單化。簡化的模型沒有了上面的步驟A和B，避免了二次改造 網(wǎng)絡，使編程容易很多。當然，代價是要多次求最大流。這個方法中用二分法，確定容量下界的最大值，求(T,S) 可能的最大流。另外，文中還提到:“在一個容量有上下界的流網(wǎng)絡G中，求源點s到匯點t的一個可行的】類似，只是在加入弧(t

18、, s)后二分(t, s)的容量上界C(t, s)即可?！笨梢娺@個簡化的方法在競賽中用途很廣。簡化方法的基本思想:設定孤(匚，)容量下界為M二分增加弓瓜|對附加網(wǎng)絡求最大流二分減少弧(T,S )的下界|J(T,S)的下界t源(或匯)相連的弧滿了嗎?1NY二分結束時 若有解：得到最大解否則：無解至此，我們已經(jīng)清楚地闡述了一個關于網(wǎng)絡流方面 的模型：對于“必要的流量”，用必要弧分離出來，用附加網(wǎng)絡3求得其上的一個可行流方案。當然，如果無解，也可 以判斷出。上面兩節(jié)，我們對流的分離和流網(wǎng)絡的等價變換做了進 步發(fā)揮。與之前所用方法技巧的比較：附加網(wǎng)絡1附加網(wǎng)絡3退流全部可退只能部分退，下 界要保證分離流：后向弧容量：必要弧-下界 容量模型轉(zhuǎn) 換直接轉(zhuǎn)換有源匯9無源 匯9有源匯劉汝佳的名著算法藝術與信息學競賽P324-P325也有這樣幾句話:“本題和流有關，但是看起來不是去求什么最大流