網(wǎng)絡(luò)流問(wèn)題實(shí)例分析

網(wǎng)絡(luò)流問(wèn)題實(shí)例分析例1【逃脫問(wèn)題】一個(gè)n*n格柵是由n行和n列結(jié)點(diǎn)組成的一個(gè)無(wú)向圖，如圖所示。我們用(i，j)表示處于第i行第j列的結(jié)點(diǎn)。除了邊界結(jié)點(diǎn)（即滿足i=1，i=n，j=1，或j=n的結(jié)點(diǎn)(i，j)），格柵中的所有其它結(jié)點(diǎn)都有四個(gè)相鄰結(jié)點(diǎn)。格柵中有m<n*2個(gè)起始點(diǎn)(x1，y1)，(x2，y2)，…(xm，ym)。一條逃脫路徑是一個(gè)起始點(diǎn)到邊界上任意一點(diǎn)的路徑。逃脫問(wèn)題就是找出最多的k條不相交的逃脫路徑，k稱為逃脫數(shù)。上圖就是k=10的逃脫方案。輸入：第1行

nm

以下m行，其中第i+1行為第i個(gè)起點(diǎn)的坐標(biāo)（xi，yi）

輸出：

一個(gè)數(shù)k，表示逃脫數(shù)。構(gòu)造一個(gè)有向圖G:由于路徑不能相交，所以每個(gè)點(diǎn)只能到達(dá)一次。為此，可以把原來(lái)每個(gè)格柵點(diǎn)(i,j)拆分成兩個(gè)頂點(diǎn)(i,j)1和(i,j)2，在它們之間連一條弧，容量設(shè)為1，表示只能到達(dá)一次。然后，如果格柵點(diǎn)(x1,y1)與(x2,y2)相鄰，則連一條弧<(x1,y1)2,(x2,y2)1>，容量為1。添加兩個(gè)點(diǎn)S,T表示源和匯，對(duì)于圖上的起始點(diǎn)和逃脫點(diǎn)（邊界上的點(diǎn)）作下面的處理:如果(x,y)是起始點(diǎn)，那么連一條弧<S,(x,y)1>，容量為1；如果(x,y)是逃脫點(diǎn)，那么連一條弧<(x,y)2,T>，容量為1。這樣，當(dāng)我們求出圖G的一個(gè)流時(shí)，它表示了一種逃脫方案，因此,求出最大流的流量就是最多能逃脫的點(diǎn)數(shù)了。構(gòu)圖

阿P與阿Q都是四驅(qū)車好手，他們各有N輛四驅(qū)車。為了一比高下，他們約好進(jìn)行一場(chǎng)比賽。這次比賽共有M個(gè)分站賽，贏得分站賽場(chǎng)次多的獲得總冠軍。每個(gè)分站賽中，兩人各選一輛自己的賽車比賽。分站賽的勝負(fù)大部分取決于兩車的性能，但由于種種原因（如相互之間的干擾），性能并不是決定勝負(fù)的唯一指標(biāo)，有時(shí)會(huì)出現(xiàn)A贏B、B贏C、C贏D、D又贏A的局面。幸好有一種高智能機(jī)器，只要給定兩輛四驅(qū)車，就能立刻判斷誰(shuí)會(huì)贏，在總比賽前它就已經(jīng)把阿p的每輛車與阿q的每輛車都兩兩測(cè)試過(guò)了，并且還把輸贏表輸入了電腦。另外，由于比賽的磨損，每輛四驅(qū)車都有自己的壽命（即它們能參加分站賽的場(chǎng)次），不同的四驅(qū)車壽命可能不同，但最多不會(huì)超過(guò)50場(chǎng)。兩輛四驅(qū)車最多只能交手一次?，F(xiàn)給定N、M（1<=N<=100，1<=M<=1000）、N*N的一個(gè)輸贏表、每輛四驅(qū)車的壽命，并假設(shè)每次分站賽兩人都有可選的賽車，請(qǐng)你計(jì)算一下阿P最多能夠贏得多少個(gè)分站賽。例2【賽車問(wèn)題】問(wèn)題描述

1、建立N個(gè)點(diǎn)代表阿P的N輛車，分別以1到N標(biāo)號(hào)；

2、建立N個(gè)點(diǎn)代表阿Q的N輛車，分別以N+1到2N標(biāo)號(hào)；

3、如果阿P的第I輛車能夠跑贏阿Q的第J輛車，則加一條弧IN+J，容量為1，表示兩輛四驅(qū)車最多只能交手一次；

4、增加一個(gè)源點(diǎn)S，S與1到N中的每一個(gè)結(jié)點(diǎn)I都連一條弧SI，容量為阿P的第I輛車的壽命；

5、增加一個(gè)匯點(diǎn)T，N+1到2N中的每一個(gè)結(jié)點(diǎn)N+J到T都連一條弧N+JT，容量為阿Q的第J輛車的壽命；

6、再增加一個(gè)源點(diǎn)S2，加一條弧S2S，容量為M，表示最多M場(chǎng)分站賽。構(gòu)圖例3【列車調(diào)度】

某貨運(yùn)車站有n（n≤20）個(gè)車道，由于車道的長(zhǎng)度有限，每個(gè)車道在某一時(shí)刻最多只能?？恳涣胸涍\(yùn)列車。車站正常運(yùn)行后，每天將有m（m≤100）列貨運(yùn)列車從車站經(jīng)過(guò)，其中第i列列車到達(dá)車站的時(shí)間為Reach[i]，列車上裝有價(jià)值Cost[i]的貨物。如果準(zhǔn)許列車i進(jìn)站，則BackStreet車站將獲得1%×Cost[i]的收益，但由于貨物的搬運(yùn)時(shí)間，該列車將在車站停留一段時(shí)間Stay[i]，這段時(shí)間內(nèi)，列車將占用車站中的某一個(gè)車道；否則列車直接出站，但這樣車站將得不到一分錢。你的任務(wù)就是：合理的安排列車的進(jìn)站與出站，使得車站的總獲利最大。

{如果列車a從第i車道離開(kāi)時(shí)，列車b剛好到站（即Reach[a]+Stay[a]=Reach[b]），則它不能進(jìn)入第i車道。}構(gòu)圖

建圖方法：

1、將每一列列車拆成兩個(gè)點(diǎn)，如第i列列車拆成點(diǎn)i和i'；i到i'之間加一條容量為1，費(fèi)用為1%×Cost[i]的弧ii'；{若ii'的弧的流量為1，則表示該列火車進(jìn)站，并獲得1%×Cost[i]}2、增加一個(gè)源點(diǎn)S，S與每個(gè)點(diǎn)i連一條容量為1費(fèi)用為0的弧Si；{如果Si的流量為1，則表示列車i作為某個(gè)車道的第一列入站的列車}3、再增加一個(gè)源點(diǎn)S’，S’S的容量為n，表示有n個(gè)車道；

4、增加一個(gè)匯點(diǎn)T，每個(gè)點(diǎn)i'與T連一條容量為1費(fèi)用為0的弧i'T；{如果i’T的流量為1，則表示列車i作為某個(gè)車道的最后一列入站的列車}5、對(duì)于所有的i和j（i≠j，且i，j∈1..m）,如果Reach[i]+Stay[i]<Reach[j]，則在i’與j之間連一條容量為1，費(fèi)用為0??；

{表示可以在某一個(gè)車道先停入列車i，等i出站后再停入列車j}

粉紅色箭頭上的數(shù)字表示費(fèi)用未標(biāo)數(shù)字的弧的費(fèi)用為0

未標(biāo)明容量的弧的容量為1優(yōu)化優(yōu)化：1.其實(shí)沒(méi)有必要增加一個(gè)源點(diǎn)S’及一條弧S’S，因?yàn)槊看涡薷目稍鰪V軌上弧的流量時(shí)，都是以1作為可修改量，故只要規(guī)定最多找n次增廣軌，就可以確保占用的車道數(shù)小于等于n了。2．第1步優(yōu)化以后，所有弧的容量都變?yōu)?，非常便于處理：可以把每條弧的容量和流量用1個(gè)Byte類型存儲(chǔ)：0——容量為0，流量為0；1——容量為1，流量為0；2——容量為1，流量為1；例4【機(jī)器人布陣】

有一個(gè)N*M(N,M<=50)的棋盤，棋盤的每一格是三種類型之一：空地、草地、墻。機(jī)器人只能放在空地上。在同一行或同一列的兩個(gè)機(jī)器人，若它們之間沒(méi)有墻，則它們可以互相攻擊。問(wèn)給定的棋盤，最多可以放置多少個(gè)機(jī)器人，使它們不能互相攻擊。墻

Wall草地

Grass

空地

Empty墻

Wall草地

Grass

空地

Empty【模型一】在問(wèn)題的原型中，草地，墻這些信息不是我們所關(guān)心的，我們關(guān)心的只是空地和空地之間的聯(lián)系。因此，我們很自然想到了下面這種簡(jiǎn)單的模型：以空地為頂點(diǎn)，有沖突的空地間連邊，我們可以得到右邊的這個(gè)圖：

問(wèn)題的求解目標(biāo)是尋求圖G的最大獨(dú)立集，即求G的獨(dú)立數(shù)α(G)。一般圖的α(G)是很難計(jì)算的，除非對(duì)于一些特殊的圖。如完全圖Kn的獨(dú)立數(shù)為n,二分完全圖Km,n的獨(dú)立數(shù)為max{m,n}。顯然這一模型不是屬于一些特殊的圖，給我們?cè)O(shè)計(jì)算法帶來(lái)很大的麻煩?！灸Ｐ投?/p>

我們將每一行，每一列被墻隔開(kāi)，且包含空地的連續(xù)區(qū)域稱作“塊”。顯然，在一個(gè)塊之中，最多只能放一個(gè)機(jī)器人。我們把水平方向的這些塊編上號(hào)；同樣，把豎直方向的塊也編上號(hào)。

123451234水平方向的塊編號(hào)豎直方向的塊編號(hào)

把每個(gè)橫向塊看作X部的點(diǎn)，豎向塊看作Y部的點(diǎn)，若兩個(gè)塊有公共的空地，則在它們之間連邊。于是，問(wèn)題轉(zhuǎn)化成這樣的一個(gè)二分圖：由于每條邊表示一個(gè)空地，有沖突的空地之間必有公共頂點(diǎn)，所以問(wèn)題轉(zhuǎn)化為二分圖的最大匹配問(wèn)題。比較前面的兩個(gè)模型：模型一過(guò)于簡(jiǎn)單，沒(méi)有給問(wèn)題的求解帶來(lái)任何便利；模型二則充分抓住了問(wèn)題的內(nèi)在聯(lián)系，巧妙地建立了二分圖模型。為什么會(huì)產(chǎn)生這種截然不同的結(jié)果呢？其一是由于對(duì)問(wèn)題分析的角度不同：模型一以空地為點(diǎn)，模型二以空地為邊；其二是由于對(duì)原型中要素的選取有差異：模型一對(duì)要素的選取不充分，模型二則保留了原型中“棋盤”這個(gè)重要的性質(zhì)。由此可見(jiàn)，要素的選取，分析角度的不同影響了理論體系的選擇。這兩點(diǎn)都是圖論建模至關(guān)重要的步驟。例5【障礙物探測(cè)車】

有一個(gè)登陸艙（POD）,里邊裝有許多障礙物探測(cè)車（MEV），將在火星表面登陸。著陸后，探測(cè)車離開(kāi)登陸艙向相距不遠(yuǎn)的先期達(dá)到的傳送器(Transmitter)移動(dòng)。MEV一邊移動(dòng)，一邊采集巖石（Rock）標(biāo)本，巖石由第一個(gè)訪問(wèn)到它的MEV采集，每塊巖石只能被采集一次。但是這之后，….問(wèn)題可簡(jiǎn)述為：在PQ的矩形中，每個(gè)格子的地形可能是下列三種之一：（1）障礙：無(wú)法通過(guò)；（2）平地：平坦無(wú)物，可通過(guò)；（3）石塊：可通過(guò)，第一次通過(guò)時(shí)可采到一塊巖石；求M條的路徑（M給定），使得路徑能夠覆蓋到石塊數(shù)總和最大，路徑要滿足的條件是：（1）每條路徑都是從(1,1)到(P,Q)，途中每步只能向東或向南走一格；（2）路徑不通過(guò)障礙。樣例輸入圖示。（探測(cè)車數(shù)M=2）

樣例輸出圖示：(覆蓋到石塊數(shù)為3)【障礙物探測(cè)車分析】1．本題的難點(diǎn)就在于多輛探測(cè)車之間的配合問(wèn)題，而對(duì)于只有一輛探測(cè)車的退化情況，應(yīng)用動(dòng)態(tài)規(guī)劃可得到最優(yōu)解:

用二維數(shù)組map[1..p,1..q]0f0..2表示火星表面情況：

map[i,j]=0表示位置（i,j）為平地；

map[i,j]=1表示位置（i,j）為障礙；

map[i,j]=2表示位置（i,j）為巖石。設(shè)S[i,j]表示探測(cè)車從（1，1）位置移動(dòng)到（i,j）位置所能夠采集到的巖石標(biāo)本數(shù)目的最大值。則有動(dòng)態(tài)規(guī)劃方程如下：S[i,j]=Max{s[i-1,j],s[i.j-1]},map[i,j]=0;0,map[i,j]=1;(1≤i≤p,1≤j≤q)Max{s[i-1,j],s[i.j-1]}+1;map[i,j]=2;邊界條件：s[i,0]=0,s[0,j]=0(1≤i≤p,1≤j≤q)2.當(dāng)m≥2時(shí)，對(duì)m輛探測(cè)車各使用一次上述的動(dòng)態(tài)規(guī)劃算法，就可以得到一個(gè)較優(yōu)解。由于這種簡(jiǎn)單的貪心沒(méi)有顧及到各探測(cè)車之間的配合，所以不能保證得到最優(yōu)解，如下面的例子：以上兩個(gè)算法都是基于一般意義的圖G〈V,E〉這一模型上考慮的，如果將一輛探測(cè)車的運(yùn)動(dòng)看作一條流，因?yàn)樘綔y(cè)車的數(shù)目一定，所以總的流量是確定的。而解的優(yōu)劣，即采集的標(biāo)本數(shù)量的多少，就只能體現(xiàn)在單位流量的“費(fèi)用”上了。因此選擇使用最小費(fèi)用最大流的方法求解。3.網(wǎng)絡(luò)流模型將圖G擴(kuò)充為一個(gè)可以求解的網(wǎng)絡(luò)模型：（1）在建圖時(shí)，可以略去所有障礙物位置，以及與(1,1)、(p,q)不連通的位置，也可看作障礙物（探測(cè)車不會(huì)經(jīng)過(guò)）。其余的位置（平地和巖石）都作為圖G的頂點(diǎn)。頂點(diǎn)集V={Vi,j│1≤i≤p,1≤j≤q,map[i,j]≠1}；有向邊集E={〈vi,j,vi+1,j〉│vi,j∈V,vi+1,j∈V}∪{〈vi,j,vi,j+1〉│vi,j∈V,vi,j+1∈V}。

（2）根據(jù)題意再把圖G擴(kuò)充為網(wǎng)絡(luò)N=〈V,E,C,R〉,C代表網(wǎng)絡(luò)中各邊的容量，R代表各邊上單位流量的費(fèi)用。由于探測(cè)車的移動(dòng)路線可以任意重疊，所以這些邊的容量C=∞，費(fèi)用R=2。（3）如何體現(xiàn)“采集巖石標(biāo)本”的特征，對(duì)于巖石頂點(diǎn)，先到的探測(cè)車采到標(biāo)本，對(duì)后到的探測(cè)車來(lái)說(shuō)就是平地，一個(gè)頂點(diǎn)怎樣來(lái)扮演兩種不同的角色？我們把巖石頂點(diǎn)Vi,j分出一個(gè)頂點(diǎn)V’I,j,并增加3條邊：

1)邊〈Vij,V’ij〉，容量C(Vij,V’ij)=1,表示標(biāo)本只能采集一次，費(fèi)用R(Vij,V’ij,)=0;2)邊〈V’ij,Vij+1〉和邊〈V’ij,Vi+1j〉，容量都是1，費(fèi)用都是1。這樣，每采集一塊巖石，對(duì)應(yīng)的流的代價(jià)就會(huì)減少1；同時(shí)，受容量的限制，每塊巖石也最多被采集一次。（4）最后再為網(wǎng)絡(luò)添加源點(diǎn)和匯點(diǎn)：因?yàn)閙輛探測(cè)車都從（1，1）出發(fā)，所以源點(diǎn)s只引出一條邊〈s,V1,1〉,容量為∞,費(fèi)用為0；類似，如果map[p,q]=0,即（p,q）處是平地，則匯點(diǎn)t也只引入一條邊〈Vp,q,t〉,容量為∞，費(fèi)用為0；如果map[p,q]=2,即該處是巖石，則多引一條邊〈V’p,q,t〉,容量為1，費(fèi)用也為1。這樣就完成了使用最小費(fèi)用最大流算法的建模。例6【蚯蚓的游戲問(wèn)題】

2

問(wèn)題描述：在一塊梯形田地上，一群蚯蚓在做收集食物游戲。蚯蚓們把梯形田地上的食物堆積整理如下：

a(1,1)a(1,2)…a(1,m)a(2,1)a(2,2)a(2,3)…a(2,m)a(2,m+1)a(3,1)a(3,2)a(3,3)…a(3,m+1)a(3,m+2)a(n,1)a(n,2)a(n,3)…a(n,m+n-1)它們把食物分成n行，第1行有m堆食物，每堆的食物量分別是a(1,1),a(1,2),…,a(1,m)；第2行有m+1堆食物，每堆的食物量分別是a(2,1),a(2,2),…,a(2,m+1)；以下依次有m+2堆、m+3堆、…、m+n-1堆食物。【蚯蚓的游戲問(wèn)題】問(wèn)題描述續(xù)1

現(xiàn)在蚯蚓們選擇了k條蚯蚓來(lái)測(cè)試它們的合作能力(1≤k≤m)。測(cè)試方法如下：第1只蚯蚓從第1行選擇一堆食物，然后往左下或右下爬，并收集1堆食物。例如從a(1,2)只能爬向a(2,2)或a(2,3)，而不能爬向其他地方。接下來(lái)再爬向下一行收集一堆食物，直到第n行收集一堆食物。第1條蚯蚓所收集到的食物量是它在每一行收集到的食物量之和；第2條蚯蚓也從第1行爬到第n行，每行收集一堆食物，爬的方法與第1條蚯蚓類似，但不能碰到第1條蚯蚓所爬的軌跡；一般地，第I條蚯蚓從第1行爬到第n行，每行收集一堆食物，爬的方法與第1條蚯蚓類似，但不能碰到前I-1條蚯蚓所爬的軌跡。這k條蚯蚓應(yīng)該如何合作，才能使它們所收集到的食物總量最多？收集到的食物總量可代表這k條蚯蚓的合作水平。

【蚯蚓的游戲問(wèn)題】問(wèn)題描述續(xù)22

編程任務(wù)：給定上述梯形m、n和k的值(1≤k≤m≤30；1≤n≤30)以及梯形中每堆食物的量（小于10的非負(fù)整數(shù)），編程計(jì)算這k條蚯蚓所能收集到的食物的最多總量2

數(shù)據(jù)輸入：輸入數(shù)據(jù)由文件名為input1.*的文本文件提供，共有n+1行。每行的兩個(gè)數(shù)據(jù)之間用一個(gè)空格隔開(kāi)。l

第1行是n、m和k的值。l

接下來(lái)的n行依次是梯形的每一行的食物量a(i,1),a(i,2),…,a(i,m+i-1),i=1,2,…,n。2

輸出：k條蚯蚓所能收集到的食物的最多總量。輸入示例輸出示例

input1.001322261250211006分析與構(gòu)圖

如果只有一條蚯蚓，我們可以用動(dòng)態(tài)規(guī)劃解決。但現(xiàn)在有k條蚯蚓，而且這些蚯蚓會(huì)相互影響（第I只蚯蚓不能碰到前I-1只蚯蚓的路線），動(dòng)態(tài)規(guī)劃難以實(shí)現(xiàn)?？紤]用網(wǎng)絡(luò)流算法來(lái)解決。

首先構(gòu)造一個(gè)初步的網(wǎng)絡(luò)流圖。我們可以把每堆食物看成一個(gè)頂點(diǎn)(x,y)，每堆食物的量用c(x,y)表示。第1行的m堆為源點(diǎn)，第n行的m+n-1堆為匯點(diǎn)。對(duì)于每個(gè)頂點(diǎn)(x,y)，添加一條弧<(x,y),(x+1,y)>，表示蚯蚓能從(x,y)向左下爬到(x+1,y)，并得到該處的食物；再添加另一條弧<(x,y),(x+1,y+1)>，表示蚯蚓能從(x,y)向右下爬到(x+1,y+1)，并得到食物。如圖1。

分析與構(gòu)圖續(xù)1考察這個(gè)圖論模型，它只能表示原題中蚯蚓的起點(diǎn)、終點(diǎn)和可行的路線，而且權(quán)值（食物量）是屬于頂點(diǎn)的。我們無(wú)法用前面的求網(wǎng)絡(luò)流的算法來(lái)解決，而且題目中一個(gè)關(guān)鍵的條件“蚯蚓爬行路線不能重疊”沒(méi)有能夠表示出來(lái)。因此我們還要對(duì)這個(gè)模型加工。

分析與構(gòu)圖續(xù)2考慮到原圖的缺陷，我們可以把每個(gè)頂點(diǎn)(x,y)拆成兩個(gè)頂點(diǎn)：(x,y)1和(x,y)2。然后按照下述規(guī)則重新構(gòu)造弧：1.

1

若原來(lái)有弧<(x1,y1),(x2,y2