網(wǎng)絡流2013版

1、1網(wǎng)絡流問題入門多年來，考察網(wǎng)絡流建模和算法的題目越來越多地出現(xiàn)在信息學競賽中，網(wǎng)絡流也已經被確定為信息學培訓的重點章節(jié)。網(wǎng)絡流問題里的構圖是最考驗做題人的思維的。題海不可取，總結是必須的。網(wǎng)絡流的學習要在學習代碼模板的基礎上，深刻理解網(wǎng)絡流模型的建立。1.1網(wǎng)絡及網(wǎng)絡流什么是網(wǎng)絡？網(wǎng)絡其實就是有向帶權圖。為什么要叫網(wǎng)絡，是因為權值是容量，容量意味著可以在單位時間內經過的上限，但是可以比上限小。有向圖=點集+有向邊集一個實例：運輸網(wǎng)絡D3SABCTE3214235圖1.1網(wǎng)絡定義：l 一個有向圖 G=(V，E)； V代表點的集合，E代表邊的集合。l 有兩個特別的點：源點s、匯點t；l 圖中每條

2、邊(u,v)E，有一個非負值的容量C(u,v)記為 G=(V，E，C)網(wǎng)絡三要素：點、邊、容量可行流定義：是網(wǎng)絡G上的一個“流”，即每條邊上有個“流量”P(u,v)，要滿足下面兩個條件：流的容量限制-?。?對任意弧(u,v)-有向邊流的平衡-點： 除源點和匯點，對任意中間點有：流入u的“流量”與流出u的“流量”相等。即： 有 網(wǎng)絡的流量：源點的凈流出“流量” 或 匯點的凈流入“流量”。即：D3SABCTE3104234111注意，我們這里說的流量是一種速率，而不是指總量。聯(lián)系上面所說的實例，下面是一個流量為1的可行流：圖1.2標準圖示法：D0/3SABCTE0/31/21/10/40/20/3

3、1/5圖1.31.2、最大流問題 尋找網(wǎng)絡G上可能的最大流量(和一個有最大流量的可行流方案)，即為網(wǎng)絡G上的最大流問題。 我們再來看看圖1.1的運輸網(wǎng)絡例子，我們可能通過改進圖1.3得到下面這樣的可行流：D1/3SABCTE1/32/21/10/40/20/31/5圖2.1 求解過程中的困惑：問題2.1流量還可能增加嗎？問題2.2如果能增加，怎樣改進？1.3、最大流算法的核心-增廣路徑退流的概念-后向弧仔細分析圖2.1，我們發(fā)現(xiàn)，流量是可以增加的：D1/3SABCTE1/31/21/11/41/21/30/5圖3.12/3把一個流量弧(B,C)和(C,T)上的流退回到B點，改道從B-D-E-T

4、走，就可以增加流量了，如下圖：2/2CA1/52/3T1/31/1S1/4B1/2ED圖3.2圖3.1不能“直接尋找增大流的路徑”，是因為當初有些弧上的流選擇不“恰當”，要“退流”。一種直觀的想法就是：調整或重新搜索“當初的選擇”-難!能不能保留以前的工作，而在這之上改進呢？經過專家們研究發(fā)現(xiàn)，加入退流思想-后向弧，就能再次“直接尋找增大流的路徑”。增廣路徑(可改進路徑)的定義 若P是網(wǎng)絡中連結源點s和匯點t的一條路，我們定義路的方向是從s到t，則路上的弧有兩種：l 前向弧-弧的方向與路的方向一致。前向弧的全體記為P+；l 后向弧-弧的方向與路的方向相反。后向弧的全體記為P-； 設F是一個可行

5、流，P 是從s到t的一條路，若P滿足下列條件：在P+的所有前向弧(u,v)上，0f(u,v) < C(u,v);在P-的所有后向弧(u,v)上，0<f(u,v) C(u,v); 則稱P是關于可行流F的一條可增廣路徑。2/2C1/31/51/3ATS0/31/10/4B0/2ED圖3.3本圖中：S-A-C-B-D-E-T 為一增廣路徑。其中(C,B)為后向弧，其它為前向弧。在增廣路徑上的改進算法：1) 求路徑可改進量；2) 修改增廣路徑上的流量；1.4、附加網(wǎng)絡1-殘留網(wǎng)絡由于要考慮前向弧、后向弧，分析、描述時不簡潔，在圖2.1上直觀看也不容易看出增廣路徑。 因此我們把已經有的流量從

6、容量中分離出來表示，引入一個與原問題等價的附加網(wǎng)絡1：殘留網(wǎng)絡。0C2122A141TS30124BED圖4.1 其中，前向弧(黑色)上的容量為“剩余容量”=C(u,v)-f(u,v)；后向弧(紅色雙線)上的容量為“可退流量”=f(v，u)。改造后的網(wǎng)如下：D2SABCTE2423411112 圖4.2 在這張圖上，我們找增廣路徑顯的非常直觀了!結合增廣路徑，我們有如下定理：最大流定理 如果殘留網(wǎng)絡上找不到增廣路徑，則當前流為最大流；反之，如果當前流不為最大流，則一定有增廣路徑。 證明涉及最小割概念，具體自己百度。 至此，問題2.1和問題2.2在這個最大流定理中同時獲得解決。求最大流的基本思想

7、： 初始化一個可行流： 現(xiàn)有網(wǎng)絡流的殘留網(wǎng)絡上有增廣路徑嗎？按上面方法對增廣路徑改進f為最大流YN基于這種思想的算法，關鍵之處在于怎樣找增廣路徑。常用方法有：l 深度搜索dfs ：Ford-Fulkerson 算法，也是入門算法。l 寬度搜索bfsl 優(yōu)先搜索pfs-即類似Dijkstra算法的標號法。1.5.最大流的代碼實現(xiàn)下面我們來學習一下dfs 求最大流的代碼實現(xiàn)：【P1318】ditch在農夫約翰的農場上，每逢下雨，Bessie最喜歡的三葉草地就積聚了一潭水。這意味著草地被水淹沒了，并且小草要繼續(xù)生長還要花相當長一段時間。因此，農夫約翰修建了一套排水系統(tǒng)來使貝茜的草地免除被大水淹沒的煩

8、惱（不用擔心，雨水會流向附近的一條小溪）。作為一名一流的技師，農夫約翰已經在每條排水溝的一端安上了控制器，這樣他可以控制流入排水溝的水流量。 農夫約翰知道每一條排水溝每分鐘可以流過的水量，和排水系統(tǒng)的準確布局（起點為水潭而終點為小溪的一張網(wǎng)）。需要注意的是，有些時候從一處到另一處不只有一條排水溝。 根據(jù)這些信息，計算從水潭排水到小溪的最大流量。對于給出的每條排水溝，雨水只能沿著一個方向流動，注意可能會出現(xiàn)雨水環(huán)形流動的情形?！据斎敫袷健康?行: 兩個用空格分開的整數(shù)N (0 <= N <= 200) 和 M (2 <= M <= 200)。N是農夫John已經挖好的排水

9、溝的數(shù)量，M是排水溝交叉點的數(shù)量。交點1是水潭，交點M是小溪。 第二行到第N+1行: 每行有三個整數(shù)，Si, Ei, 和 Ci。Si 和 Ei (1 <= Si, Ei <= M) 指明排水溝兩端的交點，雨水從Si 流向Ei。Ci (0 <= Ci <= 10,000,000)是這條排水溝的最大容量?！据敵龈袷健恳粋€整數(shù)，即排水的最大流量?！痉治觥窟@道題就是一道最基本的網(wǎng)絡流，只需要按照要求建立網(wǎng)絡模型，求出最大值即可。最大流的最基礎寫法如下，具體細節(jié)看注釋。using namespace std;const int oo=1000000;int n,m,a300030

10、00,sum=0,forward; bool vis3000,check=true;void init()cin>>m>>n;memset(a,0,sizeof(a);for (int i=1;i<=m;i+)int x,y,z;cin>>x>>y>>z;axy+=z; /這是圖論里經常出現(xiàn)的吭，表示可能出現(xiàn)重邊。void dfs(int k,int l) /k是頂點的編號，l是最小的增廣流量visk=true; /dfs必須有的標記if (k=n) /找到匯點，check=true; /全局變量，標記存在增廣路徑sum+=l;

11、 forward=l; /流量可以擴充l。并記錄下l，在回溯時進行流量操作。return;for (int i=1;i<=n;i+)if (aki>0)&&(!visi) /dfs固有的東西。dfs(i,min(aki,l);if (check) /這里是dfs后，回溯的位置aki-=forward; /正向減去流量aik+=forward; /逆向（可退流邊）加上這個流量return;int main() init(); while (check) /只要還能找到可增廣路，就一直找下去。 check=false; memset(vis,false,sizeof(v

12、is); dfs(1,oo); cout<<sum<<endl; return 0; 通過以上代碼，我們可以知道：1） 鄰接矩陣寫網(wǎng)絡流是最簡單的，因為正向邊和逆向邊都存在鄰接矩陣里。2） dfs的回溯來進行路徑的增廣，這樣的寫法是最簡潔的。這個回溯用法和并查集的回溯用法是很經典的。我們本著一題多用的原則，思考一下，如何用鄰接表來寫這道題。如果要用鄰接表寫，需要注意幾個問題：1）鄰接矩陣的反向退流邊還在鄰接矩陣里，但是鄰接表的退流邊不是固定存在的，對于每條正向邊，我們必須要新建一個和這條邊對應的退流邊。2）在建圖的時候，先插入正向邊，順便再插入退流邊，退流邊的權值為0，

13、并且給每條邊再增加一個rev域，表示這條邊的反向邊的下標是多少，這樣在流量減少的時候，順便把反向邊的流量增加上去。2 關于網(wǎng)絡流建圖的相關例題【oj1319】 N（3<=N<=200）頭奶牛要辦一個新年晚會。每頭牛都會燒幾道菜。一共有D(5<=D<=100)道不同的菜肴。每道菜都可以用一個1到D之間的數(shù)來表示。晚會的主辦者希望能盡量多的菜肴被帶到晚會，但是每道菜的數(shù)目又給出了限制。每頭奶?？梢詭(1<=K<=5)道菜，但是必須是各不相同的（例如，一頭牛不能帶三塊餡餅，但是可以帶上一塊餡餅，一份面包，和一些美味的桔子醬苜蓿）。那么，究竟有多少菜可以被帶來晚會

14、呢？例如：有4頭奶牛，每頭奶牛最多可以帶3盤食品。一共有5種食品，它們的數(shù)量上限是2、2、2、2、3。奶牛1會做食品14，奶牛2會做食品25，奶牛3會做食品1、2、4，奶牛4會做食品13。那么最多可以帶9盤食品到晚會上。即奶牛1做食品24，奶牛2做食品35，奶牛3做食品1、2，奶牛4做食品1。這樣，4種食品各有2、2、2、2、1盤。 【分析】我們嘗試建立一個有向圖，通過流量限制來構圖，并用網(wǎng)絡流來解決它。如上面的例子，我們嘗試建立下面的圖。邊：S=>奶牛, 保證每頭奶牛帶的食品的最大量。邊：食品=>T, 保證每種食品的最大數(shù)量。食品的總盤數(shù)最大值=S到T的最大流S到T的最大流=9.

15、這道題需要好好理解一下，并思考網(wǎng)絡流建圖的規(guī)則，經驗都是積累出來的。【oj1324】農夫JOHN為牛們做了很好的食品,但是牛吃飯很挑食. 每一頭牛只喜歡吃一些食品和飲料而別的一概不吃.雖然他不一定能把所有牛喂飽,他還是想讓盡可能多的牛吃到他們喜歡的食品和飲料.農夫JOHN做了F (1 <= F <= 100) 種食品并準備了D (1 <= D <= 100) 種飲料. 他的N (1 <= N <= 100)頭牛都以決定了是否愿意吃某種食物和喝某種飲料. 農夫JOHN想給每一頭牛一種食品和一種飲料,使得盡可能多的牛得到喜歡的食物和飲料.每一件食物和飲料只能由一

16、頭牛來用. 例如如果食物2被一頭牛吃掉了,沒有別的牛能吃食物2.【分析】由于有 N 只奶牛、F 種食物和 D 種飲料，因此我們可以將這些東西抽象成圖 中的點。為了方便，我們將食物放在左邊，奶牛放在中間，飲料放在右邊。沿用前面的建模方式，由于食物和飲料的使用限制，我們從源點向每種食物連一條邊， 從每種飲料向匯點連一條邊，容量都為 1。而每只奶牛都有喜歡的食物和飲料， 因此將每只奶牛喜歡的食物連到這只奶牛，從這只奶牛連到每種它喜歡的飲料。但這樣是否就對了呢？實際還是有問題的，因為經過每只奶牛的食物可能超 過一種，這就意味著每只奶牛可能會吃超過一組的食物和飲料，而這在題目中是 不允許的。怎 么 解

17、決 這 個 問 題 呢 ？ 我 們 又 回 到 了 流 的 基 本 性 質 ： 容 量 限 制f (u, v) £ c(u, v) 。因此我們將每只奶牛拆成兩個點，同一只奶牛的兩個點之間連 邊，容量為 1。這樣我們就能保證通過每只奶牛的流量為 1 了。每個流對應每種方案，最大流即為最佳方案?？梢娮畲罅髂Ｐ偷囊话憬Ｋ悸肥沁\用流的容量限制，使得題目中的約束得以滿足，有時還需使用一些特殊的方法（如上題中的拆點）來滿足題目的特別約 束?！緊j1609】尼克在一家養(yǎng)豬場工作，這家養(yǎng)豬場共有M間鎖起來的豬舍，由于豬舍的鑰匙都給了客戶，所以尼克沒有辦法打開這些豬舍，客戶們從早上開始一個接一個來購

18、買生豬，他們到達后首先用手中的鑰匙打開他所能打開的全部豬舍，然后從中選取他要買的生豬，尼克可以在此期間將打開的豬舍中的豬調整到其它開著的豬舍中，每個豬舍能存放的豬的數(shù)量是沒有任何限制的。買完豬后客戶會將他打開的豬舍關上。好在尼克事先知道每位客戶手中有哪些鑰匙，要買多少豬，以及客戶到來的先后次序。請你寫一個程序，幫助尼克求出最多能賣出多少頭生豬。【分析】網(wǎng)絡流的建圖是很難得，福建師大附中的江鵬在論文從一道題目的解法試談網(wǎng)絡流的構造與算法的引論中也有這樣一句話： “網(wǎng)絡流在具體問題中的應用，最具挑戰(zhàn)性的部分是模型的構造。這沒用現(xiàn)成的模式可以套用，需要對各種網(wǎng)絡流的性質了如指掌（比如點有容量、容量有

19、上下限、多重邊等等），并且歸納總結一些經驗，發(fā)揮我們的創(chuàng)造性?！? 最小割3.1 一些相關概念1到底什么是割：原始點集為V，選出一些點集S使得sS，T=V-S，tT，則S到T的邊為S到T割，記做S,T。2什么是最小割：圖中所有的割中，邊權值和最小的割為最小割！上圖一個割的例子，邊的數(shù)字代表邊的容量，割的容量是2+2+1+6=113割的容量容量和流量計算的區(qū)別：割S,T的容量為(邊(u,v)的容量和)，其中uS,T。也就是說割的容量不計算反向的邊！而流量為正向的和反向的代數(shù)和。4. 怎樣求割 求完最大流后，在殘留網(wǎng)絡中從source開始dfs，被染色的為S，未被染色的為T，則邊集S,T為割。 5

20、最大流-最小割定理：最大流的值為最小割的容量！（反證法）通俗簡明的講：“最大流小于等于最小割”。這是“流理論”里最基礎最重要的定理。整個“流”的理論系統(tǒng)都是在這個定理上建立起來的，必須特別重視。下面我們給出證明。證明 對任意一個中間點（即非S、也非T的點）vi，恒有： （1）當vi = S時有 （2）從（1）、（2）對iU求和得因為：V = UW，所以又因： 即 故有：所以即V(f) C(U,W)命題得證。這里得證明是為了加深對最小割的了解。建議在腦子很清楚的條件下研讀。網(wǎng)絡流、可改進路、割切都是基礎的概念，應該扎實掌握。它們三者之間乍一看似乎風馬牛不相干，其實內在聯(lián)系是十分緊密的。3.2 最

21、小割入門例題【OJ1320】patrolFJ有個農場，其中有n塊土地，由m條邊連起來。FJ的養(yǎng)牛場在土地1，在土地n有個新開張的雪糕店。Bessie經常偷偷溜到雪糕店，當Bessie去的時候，F(xiàn)J就要跟上她。但是Bessie很聰明，她在從雪糕店返回時不會經過去雪糕店時經過的農場，因此FJ總是抓不住Bessie。為了防止Bessie生病，F(xiàn)J決定把一些誠實的狗放在一些土地(1和n除外)上，使Bessie無法在滿足每塊土地最多只經過一次的條件的情況下，從養(yǎng)牛場溜到雪糕店然后又溜回養(yǎng)牛場。求出FJ最少要放多少只狗。數(shù)據(jù)保證1和n間沒有直接的連邊?！痉治觥孔钚「钋蟮氖歉钸?，而這里求的是割點，怎么辦？這

22、里的條件是 Bessie無法在滿足每塊土地最多只經過一次的條件的情況下 是我們的突破口。根據(jù)1324的經驗，我們把每一個點拆成兩個點，入點和出點，且入點到出點的流量為1.這樣求一個最大流，得到的就是最小割。思考幾個問題：1） 其他邊的流量是多少？2） 用鄰接矩陣是否可行?！緊j1341】被污染的牛奶 milk6你第一天接手三鹿牛奶公司就發(fā)生了一件倒霉的事情：公司不小心發(fā)送了一批有三聚氰胺的牛奶。很不幸，你發(fā)現(xiàn)這件事的時候，有三聚氰胺的牛奶已經進入了送貨網(wǎng)。這個送貨網(wǎng)很大，而且關系復雜。你知道這批牛奶要發(fā)給哪個零售商，但是要把這批牛奶送到他手中有許多種途徑。送貨網(wǎng)由一些倉庫和運輸卡車組成，每輛卡

23、車都在各自固定的兩個倉庫之間單向運輸牛奶。在追查這些有三聚氰胺的牛奶的時候，有必要保證它不被送到零售商手里，所以必須使某些運輸卡車停止運輸，但是停止每輛卡車都會有一定的經濟損失。你的任務是，在保證壞牛奶不送到零售商的前提下，制定出停止卡車運輸?shù)姆桨?，使損失最小。輸入格式：第一行: 兩個整數(shù)N(2<=N<=32)、M(0<=M<=1000), N表示倉庫的數(shù)目，M表示運輸卡車的數(shù)量。倉庫1代 表發(fā)貨工廠，倉庫N代表有三聚氰胺的牛奶要發(fā)往的零售商。 第2.M+1行: 每行3個整數(shù)Si,Ei,Ci。其中Si,Ei表示這 輛卡車的出發(fā)倉庫，目的倉庫。Ci(0 <= C i

24、 <= 2,000,000) 表示讓這輛卡車停止運輸?shù)膿p失。輸出格式：第1行兩個整數(shù)c、t,c表示最小的損失，T表示要停止的最少卡車數(shù)。接下來t 行表示你要停止哪幾條線路。如果有多種方案使損失最小，輸出停止的線路最少的方案。如果仍然還有相同的方案，請選擇開始輸入順序最小的?！痉治觥勘镜李}就是要求最小割，那么求出最大流就是最小割，但是還要輸出最小割最少包含的邊的個數(shù)和方案。關鍵是是求出最小割邊集合最少包含邊的個數(shù)，標程用了一種很不錯的方法。因為總共只有1000條邊，那么將每個邊容量*1001+1作為新的容量（注意這里指每次讀入的每個邊），那么最大流mod 1001就是最小割去的邊數(shù)。最大流

25、=值 div 1001。首先這對最大流求肯定沒影響，其次，我們知道對以每一條增廣路大小取決于最小的那個，這里的+1就派上了用場。 在同樣可一減去2條邊和減去一條邊使其不連通時，減去兩條邊對應+2>+1所以，求最大流時會選擇+1 ，同樣，對于那些必須刪的邊多少個+1其實就等于刪了多少條邊。再按編號從小往大的順序枚舉每條邊，判斷去掉之后最大流減小值是否等于邊權。是則輸出?！揪毩曨}OJ1342】農夫約翰的奶牛們喜歡通過電郵保持聯(lián)系，于是她們建立了一個奶牛電腦網(wǎng)絡，以便互相交流。這些機器用如下的方式發(fā)送電郵：如果存在一個由c臺電腦組成的序列a1,a2,.,a(c)，且a1與a2相連，a2與a3相

26、連，等等，那么電腦a1和a(c)就可以互發(fā)電郵。 很不幸，有時候奶牛會不小心踩到電腦上，農夫約翰的車也可能碾過電腦，這臺倒霉的電腦就會壞掉。這意味著這臺電腦不能再發(fā)送電郵了，于是與這臺電腦相關的連接也就不可用了。 有兩頭奶牛就想：如果我們兩個不能互發(fā)電郵，至少需要壞掉多少臺電腦呢？請編寫一個程序為她們計算這個最小值和與之對應的壞掉的電腦集合。 以如下網(wǎng)絡為例： 1* / 3 - 2*這張圖畫的是有2條連接的3臺電腦。我們想要在電腦1和2之間傳送信息。電腦1與3、2與3直接連通。如果電腦3壞了，電腦1與2便不能互發(fā)信息了。3.3網(wǎng)絡流關鍵割邊 定義：關鍵割邊就是增加某條邊的容量,可以使得網(wǎng)絡的最

27、大流增加。 算法描述：首先對這個網(wǎng)絡圖跑一遍dinic（最大流），得到殘余網(wǎng)絡。再分別從s和t對殘余網(wǎng)絡進行dfs。對于一條邊(a,b)如果從s可以到達a并且從t可以到達b則該邊為關鍵割邊。注意，滿流的邊不一定是關鍵割邊。具體反例見胡波濤論文第8頁。3.4一些割的性質 1.割S,T，流量只能從S流向T，不能從T流向S！ （在最大流后找割dfs時其實就滿足這個性質，假設T中一個點v流向S中的一個點u，那么u到v有負流量，則u到v的殘留網(wǎng)絡嚴格大于0。 ）2.最大流后，割邊一定滿流。減小某一割邊后，網(wǎng)絡流減小。 3.如下圖，從s沿著殘余流量dfs，得到點集S；同理沿著t反向dfs，得到點

28、集T；剩下的是M。分界線cut1和cut2是其中一割，邊自然為割邊。然而在M中還存有割邊（一定存有！否則M就沒用了?。?4. 退化一下：如下圖所示，S和T有相鄰部分邊集E1，S和M重合邊集相鄰部分邊集E2，M和T相鄰邊集部分E3，那么直接升高E1中某條邊的容量，會使整體容量直接增高！反之：而如果增大S和M相鄰的割邊或者M和T相鄰的割邊，網(wǎng)絡流不直接增大，因為M中還存有割邊限制 。繼續(xù)退化：如果M=空集，cut1和cut2重合（變?yōu)閏ut），則網(wǎng)絡中割唯一?？梢酝ㄟ^ if ( |S|+|T|=總點數(shù)) 來判斷 3.5 最大權閉合圖以下內容參考 胡伯濤 最小割模型在信息學競賽中的應用，感謝他為我們

29、提供這么優(yōu)秀的論文。 看不懂以上論文的同學，可以試試看一下以下內容，本文無大量的數(shù)學符號，方便閱讀理解。 首先我們由一道題來引入，見 OJP1343 太空飛行計劃問題 。 這道題中，實驗依賴于儀器，而實驗和儀器都有權值，且儀器為負，實驗為正。 這里閉合圖的概念就很好引出了。在一個圖中，我們選取一些點構成集合，記為V，且集合中的出邊(即集合中的點的向外連出的弧)，所指向的終點(弧頭)也在V中，則我們稱V為閉合圖。最大權閉合圖即在所有閉合圖中，集合中點的權值之和最大的V，我們稱V為最大權閉合圖。 左圖中閉合圖有 5、2,5、4,5 2,4,5、3,4,5 1,2,3,4,5、1,2,4,5 最大權

30、閉合圖為3,4,5。 針對本題而言，我們將實驗與儀器間連一條有向邊，實驗為起點(弧尾)，儀器為終點(弧頭)。則如果我們選擇一個閉合圖，那么這個閉合圖中包含的實驗所需要的儀器也最這個閉合圖里。而最大權閉合圖即為題目的解。 了解了最大權閉合圖的概念，接下來我們就需要知道如何求最大權閉合圖。 首先我們將其轉化為一個網(wǎng)絡(現(xiàn)在不要問為什么,接下來會證明用網(wǎng)絡可以求解)。構造一個源點S，匯點T。我們將S與所有權值為正的點連一條容量為其權值的邊，將所有權值為負的點與T連一條容量為其權值的絕對值的邊，原來的邊將其容量定為正無窮。 上圖即被轉化為如左圖網(wǎng)絡。 首先引入結論，最小割所產生的兩個集合中，其源點S所

31、在集合(除去S)為最大權閉合圖，接下來我們來說明一些結論。?證明:最小割為簡單割。 引入一下簡單割的概念：割集的每條邊都與S或T關聯(lián)。(請下面閱讀時一定分清最小割與簡單割，容易混淆) 那么為什么最小割是簡單割呢？因為除S和T之外的點間的邊的容量是正無窮，最小割的容量不可能為正無窮。所以，得證。?證明網(wǎng)絡中的簡單割與原圖中閉合圖存在一一對應的關系。(即所有閉合圖都是簡單割，簡單割也必定是一個閉合圖)。 證明閉合圖是簡單割：如果閉合圖不是簡單割(反證法)。那么說明有一條邊是容量為正無窮的邊，則說明閉合圖中有一條出邊的終點不在閉合圖中，矛盾。 證明簡單割是閉合圖：因為簡單割不含正無窮的邊，所以不含有

32、連向另一個集合(除T)的點，所以其出邊的終點都在簡單割中，滿足閉合圖定義。得正。?證明最小割所產生的兩個集合中，其源點S所在集合(除去S)為最大權閉合圖。 首先我們記一個簡單割的容量為C,且S所在集合為N，T所在集合為M。 則C=M中所有權值為正的點的權值(即S與M中點相連的邊的容量)+N中所有權值為負的點權值的絕對值(即N中點與T中點相連邊的容量)。記(C=x1+y1);(很好理解，不理解畫一個圖或想象一下就明白了)。 我們記N這個閉合圖的權值和為W。 則W=N中權值為正的點的權值-N中權值為負的點的權值的絕對值。記(W=x2-y2); 則W+C=x1+y1+x2-y2。 因為明顯y1=y2

33、，所以W+C=x1+x2; x1為M中所有權值為正的點的權值，x2為N中權值為正的點的權值。 所以x1+x2=所有權值為正的點的權值之和(記為TOT). 所以我們得到W+C=TOT.整理一下W=TOT-C. 到這里我們就得到了閉合圖的權值與簡單割的容量的關系。 因為TOT為定值，所以我們欲使W最大，即C最小，即此時這個簡單割為最小割，此時閉合圖為其源點S所在集合(除去S)。得正。 至此，我們就將最大權閉合圖問題轉化為了求最小割的問題。求最小割用最小割容量=最大流，即可將問題轉化為求最大流的問題。最大權閉合圖練習： P1344 P17334 dinic 算法dinic算法要比上面Ford-Ful

34、kerson算法效率要高一些。我們看下面的例子：我們知道，F(xiàn)ord-Fulkerson算法是每次找到一條增廣路徑，這個圖中如果用Ford-Fulkerson算法，23這條邊的退流將會做9999次，極大的影響算法的效率。而dinic算法確可以有效的解決這個問題。下面的講解只講解dinic的基本原理和實現(xiàn)，不太糾結于證明。假設有以下的這幅圖：先bfs一遍（注意只遍歷容量不為0的邊），求出所有節(jié)點的層數(shù)，用level數(shù)組記錄。 接著就做網(wǎng)絡流，其基本原理就是：在現(xiàn)有的level基礎上，只按照level遞增順序找增廣路徑，且有一點不同的是當找到一條s->t的路徑的時候，不是直接結束，而

35、是從當前路徑上最小層次的頂點（頂點，當前路徑最大流量的邊上的點，就是下圖的紅點或綠點K）再次尋找可行流（一定要將當前層次的可行流全部找完啊?。鞠旅娴脑砻枋鰜碜試壹栮犝撐摹空麄€dfs過程分為2個操作。如果p的最后一個頂點為匯點，也就是說找到了增廣路，那么對p增廣，注意到增廣后一定有一條或多條p中的邊被刪除了。這時，我們使增廣路徑后退至p中從源點可到達的最后一個頂點。如果p的最后一個頂點不為匯點，那么觀察最后那個的頂點u 。若在層次圖中存在從u連出的一條邊，比如(u,v)，我們就將頂點v放入路徑p中，繼續(xù)dfs遍歷；否則，點u對之后的dfs遍歷就沒有用了，我們將點u以及層次圖中連到u的所有

36、邊刪除，并且在p中后退一個點。Dfs過程將會不斷重復這2個操作，直到從源點連出的邊全部被刪除為止。整個dinic的過程就是不斷地先bfs，再dfs，直到bfs不能得到匯點的層數(shù)為止。下面給出一個dfs的圖例，圖中，紅邊代表找到的增廣路p中的邊。具體代碼實現(xiàn)如下，我用的題目是usaco ditch 加強版的數(shù)據(jù)。用這個算法，套用最大權閉合圖，就可以A掉noi06年最大獲利那道題。自我感覺，dinic用幾遍后，代碼實現(xiàn)應該沒有問題。5 費用流最大流問題要求從源點S流出盡可能多的流量，流過一條或多條邊，到達匯點T，且每條邊上流過的流量不大于該邊的流量限制，一個單位的流在某條邊上產生的費用等于邊的費用

37、。而最小費用最大流問題就是要求在流量達到最大的情況下，總費用最小。由最大流的相關知識可知，當且僅當不存在S到T的增廣路時，圖中的流達到最大。那么我們可以每次從S流出一個單位的流量到達T，使得這個單位流量所產生的費用最小。從“形”的角度觀察這個問題，每個單位的流在當前網(wǎng)絡中產生的最小費用，等價于當前網(wǎng)絡中S到T的最小權值路徑的權值，即S到T最短路的長度。因此，可以用SPFA求最短路，每次選擇殘留網(wǎng)絡中最短的增廣路進行增廣，直到不存在增廣路為止，可以證明找到的最大流的費用一定最小。分析這個算法的時間復雜度，如果增廣次數(shù)是w，每次SPFA算法在殘留網(wǎng)絡G上的運行時間是SPFA(G)，那么總的時間復雜

38、度就是O(w×SPFA(G)。用流量控制連通，每次找費用最小的增廣路徑，這樣得到的最大流肯定是費用最小的。這是我對費用流的理解。Noip2008 傳紙條因為要找兩條不相交的路徑讓費用最大，我們可以利用費用流的模板來完成。讓起點的流量為2，這樣就可以約束只找兩條路徑，把費用變成負的，這樣將最大費用改為最小費用。因為有向邊，不會有流量環(huán)，我們可以將spfa的迭代改為大于號也行。下面是費用流的模板，希望認真研讀。費用流例子：Sdoi 2009 晨跑要求一個路口不能經過兩次以上。那么就把每個點拆成兩個分別放在A部和B部里面。對于每個輸入的x,y,z連一條Ax，By，流量為1，費用為z的邊。再

39、從每個Bi向Ai連一條流量為1，費用為0的邊控制只能走一次。源即1，匯為n+n。SDOI2010星際競速這是道圖論題是肯定的，圖都給你了那么問題在于如何建模問題要求訪問每個點恰好一次（我一開始沒看到這個條件）要求總時間最短，嘗試把問題轉化為一些經典圖論問題比如最短路很可惜不行，那么自然想到網(wǎng)絡流（組里面有句戲言叫“一切皆可網(wǎng)絡流”，比如A+B）進一步分析發(fā)現(xiàn)單純的網(wǎng)絡流是不行的，需要用費用流訪問每個點恰好一次，跟路徑覆蓋其實有點像把每個星球拆成兩個點，u和u'我們對每條題目給定的邊(u,v)，在網(wǎng)絡流中加一條邊(u,v')，流量為1，費用為時間然后第一次可以前往任何一個點，那么

40、從st向v'連一條邊，流量為1，費用為定位時間從每個v'向ed連一條邊，容量為1，費用為0，表示每個點的的入度為1，僅會訪問一次從st向每個u連一條邊，容量為1，費用為0，以便u通過(u,v')到達v'那么這個圖的最小費用流就是答案ZJOI2010network 求平均費用這個有點無趣啊。人數(shù)給定了其實只要求出最少的總時間花費就行了、不用搞什么分數(shù)規(guī)劃。 這題費用流的算法是很明顯的啦、就是構圖很巧妙 N輛車，M個工人。 把每個工人拆成N個點。記為Ai,j表示第i個工人修倒數(shù)第j輛車。每個車跟所有N*M個工人拆出的點連邊。流

41、量為1，費用為timei,j*k。源和每輛車連邊，N*M個點和匯連邊，流量都為1，費用同為0。 為什么這么構圖呢？ 考慮第i個工人，他修第j輛車只對后面要修的車有影響，而前面修過的車已經對當前沒有影響了。而這個影響就是后面每個將要修理的車都多等待了time的時間。 其他邊流量都為1是顯然的，每輛車修一次，每個工人一個時段只能修理一輛車。 跑一遍費用流，出解、【閱讀材料】網(wǎng)絡流問題可以說是OI中最靈活的問題之一了，建模方法很多，但還是有一定規(guī)律的囧網(wǎng)絡流建模主要分為兩類：直接用最大流建模、用最大流最小割定理轉化為最小割來建模。這里主要總結的是前一種。（1）

42、增廣路思想：應用范圍較小，但是確實有一些模型用增廣路思想很容易解釋，用流量平衡思想?yún)s很難解釋（比如下面舉的例子）。增廣路思想可以概括為：原題的方案的得出可以很明顯地分為一些階段，每一階段都會對一些變量（這些變量可能是實的也可能是虛設的）產生同樣的效果值累加，而這些變量恰好有各自的限制，且互不關聯(lián)。這剛好相當于網(wǎng)絡中的一條從源點到匯點的一條增廣路，對路上所有邊的流量都會增加，且流量有各自限制（容量），且互不關聯(lián)。并且，該模型滿足下面（3）中的兩條原則（可行性原則和最優(yōu)性原則）。在比較多的時候，用增廣路思想能夠解釋的模型往往是一個很明顯的“物質路徑”模型，某一種物質（可以是實的也可以是虛的）從源點

43、往匯點“走”，邊上的流量代表物質經過的量。例1：NOIP2011觀光公交首先，由于來出發(fā)地的時間已知且一定，所以“旅行時間總和最小”其實就是所有人下車的時間總和盡可能小，因此，先求出在不用任何加速器（初始）情況下，到達每一站的時間，設為Si，又設Mi為在第i站上車的來的最晚的人來的時間，則很顯然可以得到初始的遞推式：Si=maxSi-1, Mi-1+Di-1（初始的D值），邊界S0=0。下面來看一下Di的減少是如何影響S值的?？聪旅孢@個例子：N=5i ： 0 1 2 3 4Di（初始）： 3 4 3 2 Mi ： 1 2 6 14 Si（初始）： 0 4 8 11 16現(xiàn)在將D0的值減小1之后

44、：i ： 0 1 2 3 4Di： 2 4 3 2 Mi： 1 2 6 14 Si： 0 3 7 10 16可以發(fā)現(xiàn)，D0值減小1之后，S1.3的值都減小了1，而S4的值不變。這是因為在D0減小1之前，對于1<=i<3均有Si>Mi，D0若減小1，顯然S1會減小1，而由于S1>M1，S1=maxS1, M1，所以S1的值減小1會使得maxS1, M1減小1，從而S2的值減小1，然后由于初始的S2>M2，同樣會使得S3減小1，而初始的S3<=M3，故S3減小1不會使得maxS3, M3發(fā)生變化，所以S4的值不會受到影響。所以，可以得到：Di減小1，會使得Si+

45、1.j+1均減小1，其中j是使任意i+1<=k<=j0均滿足Sk（減小前）>Mk的最大的j0值。從這個當中可以發(fā)現(xiàn)，對于原題的每一個可行方案，必然都是分為若干個階段，其中每一階段是將某個Di值減小1（當然，要滿足Di在減小前>0），每一階段進行后都會將從Si+1開始的連續(xù)的一段S值都減小1，恰好可以抽象成一條連續(xù)的路徑，又因為當Si減小到<=Mi的時候就必須停止了（準確來說是不能再往后延伸了），所以每個Si的能夠繼續(xù)延伸的減小的量都是有限的，為初始的Si-Mi（如果這個值<0，則取0），剛好是一個上限。這很明顯是增廣路思想。所以，經過整理，可以建立一個網(wǎng)絡流

46、模型：<1>設立兩個源點s和s'（其中s是真正的源點）及匯點t，連邊<s, s'>，容量為K，費用為0，表示最多只能有K個階段；<2>將每一站i拆成兩個點i'和i''，連邊<i', i''>，容量為max(Si-Mi, 0)，費用為0，表示該點最多只能接受max(Si-Mi, 0)次加速器作用；<3>對于所有的i滿足1<=i<N，連邊<(i-1)'', i'>，容量為INF，費用為第i站下車的人數(shù)（這是因為即使Si<=

47、Mi，加速器對于本站仍然有效，只是不能繼續(xù)延伸，所以表示加速器起的效果的邊應該在本站的限制之前）；<4>對于所有的i滿足0<=i<N-1，連邊<s', i''>，容量為初始Di，費用為0，表示使用加速器的地方，從下一站開始對Si起效果；<5>對于所有的i滿足1<=i<N，連邊<i', t>，容量為INF，費用為0，表示加速器作用的結束。（其實，0'和(N-1)''這兩個點是木有任何意義的，可以從圖中刪掉）這樣，每一階段加速器的作用都可以表示為一條從s到t的增廣路，該網(wǎng)

48、絡流模型中的各種限制也反應了題目中的限制。對該網(wǎng)絡求最大費用最大流，得到的總的最大費用從初始的總旅行時間中減去（注意總旅行時間是long long的），即為答案?？梢宰C明，這個模型符合“兩條原則”，所以是正確的。（2）流量平衡思想：這個思想的應用非常廣，可以解釋絕大多數(shù)網(wǎng)絡流模型。所謂流量平衡，就是指在一個可行流里，除了源點和匯點外，其余每個點的入邊流量總和都等于出邊流量總和。可以證明，一個流是可行流當且僅當其：（1）每條邊的流量都不超過容量限制；（2）符合流量平衡。流量平衡思想的主要用處是：可以把圖中的每條邊的流量（當然必須是非負的）都想像為一個變量的值，對于每個點，滿足流量平衡，也就是一些

49、變量的和值滿足某種等量關系，如果這些等量關系剛好能夠反映題目中的所有信息，邊的容量限制也反映題目中的條件，且這個模型符合“兩條原則”，則該模型就是正確的了。在建模的時候，應先單獨考慮各個點，找到它們的所有入邊和出邊代表的變量是什么，然后再將這些邊合并，構成圖。在用流量平衡建模時有一些技巧：<1>要注意每條邊都同時作為一個點的出邊和一個點的入邊，因此，每個變量必然同時關聯(lián)兩個等量關系，且分別出現(xiàn)在這兩個等量關系的等號的左邊和右邊（或者是以一對相反數(shù)形式出現(xiàn)）；<2>如果題目中給出的變量和值關系不是等量關系，而是不等關系，那么可以將剩余的流量通過從源點或往匯點連邊的辦法，使

50、其平衡。比如，若題目中有y1+y2>=x1+x2>=y1+y2-5這樣的關系，則可以這樣做：設置一個點，將y1、y2代表的邊作為該點的入邊，將x1、x2代表的邊作為該點的出邊，然后從該點往匯點連一條容量為5的邊；<3>如果點內部有限制（比如某個點自身的權值不能超過X等等），那么該點內部也“暗含”一個變量，此時就需要拆點（不一定拆成兩個點，可能拆成更多的點），然后在拆出的點當中再連邊，附加一些限制，然后再考慮流量平衡；<4>如果一條邊有上下界，且上下界相等（也就是該邊的流量已經定死了），則可以改裝成費用流，將這條邊的費用設為一個絕對值很大的負數(shù)，這樣就肯定能保證該邊滿流了。例2：餐巾計劃問題（經典問題）這個的模型用增廣路思想根本就不能解釋。其實，可以用增廣路思想建立一個模型，但是是錯誤的，可以用下面的“兩條原則”檢查出來。&