網(wǎng)絡(luò)流2013版

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

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

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

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

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是關(guān)于可行流F的一條可增廣路徑。2/2C1/31/51/3ATS0/31/10/4B0/2ED圖3.3本圖中：S-A-C-B-D-E-T 為一增廣路徑。其中(C,B)為后向弧，其它為前向弧。在增廣路徑上的改進(jìn)算法：1) 求路徑可改進(jìn)量；2) 修改增廣路徑上的流量；1.4、附加網(wǎng)絡(luò)1-殘留網(wǎng)絡(luò)由于要考慮前向弧、后向弧，分析、描述時(shí)不簡(jiǎn)潔，在圖2.1上直觀看也不容易看出增廣路徑。 因此我們把已經(jīng)有的流量從

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

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

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

9、溝的數(shù)量，M是排水溝交叉點(diǎn)的數(shù)量。交點(diǎn)1是水潭，交點(diǎn)M是小溪。 第二行到第N+1行: 每行有三個(gè)整數(shù)，Si, Ei, 和 Ci。Si 和 Ei (1 <= Si, Ei <= M) 指明排水溝兩端的交點(diǎn)，雨水從Si 流向Ei。Ci (0 <= Ci <= 10,000,000)是這條排水溝的最大容量。【輸出格式】一個(gè)整數(shù)，即排水的最大流量?！痉治觥窟@道題就是一道最基本的網(wǎng)絡(luò)流，只需要按照要求建立網(wǎng)絡(luò)模型，求出最大值即可。最大流的最基礎(chǔ)寫法如下，具體細(xì)節(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; /這是圖論里經(jīng)常出現(xiàn)的吭，表示可能出現(xiàn)重邊。void dfs(int k,int l) /k是頂點(diǎn)的編號(hào)，l是最小的增廣流量visk=true; /dfs必須有的標(biāo)記if (k=n) /找到匯點(diǎn)，check=true; /全局變量，標(biāo)記存在增廣路徑sum+=l;

11、 forward=l; /流量可以擴(kuò)充l。并記錄下l，在回溯時(shí)進(jìn)行流量操作。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; /逆向（可退流邊）加上這個(gè)流量return;int main() init(); while (check) /只要還能找到可增廣路，就一直找下去。 check=false; memset(vis,false,sizeof(v

12、is); dfs(1,oo); cout<<sum<<endl; return 0; 通過(guò)以上代碼，我們可以知道：1） 鄰接矩陣寫網(wǎng)絡(luò)流是最簡(jiǎn)單的，因?yàn)檎蜻吅湍嫦蜻叾即嬖卩徑泳仃嚴(yán)铩?） dfs的回溯來(lái)進(jìn)行路徑的增廣，這樣的寫法是最簡(jiǎn)潔的。這個(gè)回溯用法和并查集的回溯用法是很經(jīng)典的。我們本著一題多用的原則，思考一下，如何用鄰接表來(lái)寫這道題。如果要用鄰接表寫，需要注意幾個(gè)問(wèn)題：1）鄰接矩陣的反向退流邊還在鄰接矩陣?yán)铮青徑颖淼耐肆鬟叢皇枪潭ù嬖诘?，?duì)于每條正向邊，我們必須要新建一個(gè)和這條邊對(duì)應(yīng)的退流邊。2）在建圖的時(shí)候，先插入正向邊，順便再插入退流邊，退流邊的權(quán)值為0，

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

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

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

16、頭牛來(lái)用. 例如如果食物2被一頭牛吃掉了,沒(méi)有別的牛能吃食物2.【分析】由于有 N 只奶牛、F 種食物和 D 種飲料，因此我們可以將這些東西抽象成圖 中的點(diǎn)。為了方便，我們將食物放在左邊，奶牛放在中間，飲料放在右邊。沿用前面的建模方式，由于食物和飲料的使用限制，我們從源點(diǎn)向每種食物連一條邊， 從每種飲料向匯點(diǎn)連一條邊，容量都為 1。而每只奶牛都有喜歡的食物和飲料， 因此將每只奶牛喜歡的食物連到這只奶牛，從這只奶牛連到每種它喜歡的飲料。但這樣是否就對(duì)了呢？實(shí)際還是有問(wèn)題的，因?yàn)榻?jīng)過(guò)每只奶牛的食物可能超 過(guò)一種，這就意味著每只奶?？赡軙?huì)吃超過(guò)一組的食物和飲料，而這在題目中是 不允許的。怎 么 解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

35、是從當(dāng)前路徑上最小層次的頂點(diǎn)（頂點(diǎn)，當(dāng)前路徑最大流量的邊上的點(diǎn)，就是下圖的紅點(diǎn)或綠點(diǎn)K）再次尋找可行流（一定要將當(dāng)前層次的可行流全部找完?。。鞠旅娴脑砻枋鰜?lái)自國(guó)家集訓(xùn)隊(duì)論文】整個(gè)dfs過(guò)程分為2個(gè)操作。如果p的最后一個(gè)頂點(diǎn)為匯點(diǎn)，也就是說(shuō)找到了增廣路，那么對(duì)p增廣，注意到增廣后一定有一條或多條p中的邊被刪除了。這時(shí)，我們使增廣路徑后退至p中從源點(diǎn)可到達(dá)的最后一個(gè)頂點(diǎn)。如果p的最后一個(gè)頂點(diǎn)不為匯點(diǎn)，那么觀察最后那個(gè)的頂點(diǎn)u 。若在層次圖中存在從u連出的一條邊，比如(u,v)，我們就將頂點(diǎn)v放入路徑p中，繼續(xù)dfs遍歷；否則，點(diǎn)u對(duì)之后的dfs遍歷就沒(méi)有用了，我們將點(diǎn)u以及層次圖中連到u的所有

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

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

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

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

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

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

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

43、往匯點(diǎn)“走”，邊上的流量代表物質(zhì)經(jīng)過(guò)的量。例1：NOIP2011觀光公交首先，由于來(lái)出發(fā)地的時(shí)間已知且一定，所以“旅行時(shí)間總和最小”其實(shí)就是所有人下車的時(shí)間總和盡可能小，因此，先求出在不用任何加速器（初始）情況下，到達(dá)每一站的時(shí)間，設(shè)為Si，又設(shè)Mi為在第i站上車的來(lái)的最晚的人來(lái)的時(shí)間，則很顯然可以得到初始的遞推式：Si=maxSi-1, Mi-1+Di-1（初始的D值），邊界S0=0。下面來(lái)看一下Di的減少是如何影響S值的?？聪旅孢@個(gè)例子：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的值不變。這是因?yàn)樵贒0減小1之前，對(duì)于1<=i<3均有Si>Mi，D0若減小1，顯然S1會(huì)減小1，而由于S1>M1，S1=maxS1, M1，所以S1的值減小1會(huì)使得maxS1, M1減小1，從而S2的值減小1，然后由于初始的S2>M2，同樣會(huì)使得S3減小1，而初始的S3<=M3，故S3減小1不會(huì)使得maxS3, M3發(fā)生變化，所以S4的值不會(huì)受到影響。所以，可以得到：Di減小1，會(huì)使得Si+

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

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

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

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

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

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