二分圖匹配與網(wǎng)絡(luò)流問題

二分圖匹配與網(wǎng)絡(luò)流問題長沙市第一中學(xué)曹利國主要內(nèi)容二分圖的定義二分圖的判定(BFS)網(wǎng)絡(luò)流二分圖的最大匹配二分圖的若干定義二分圖無向圖中，把所有頂點(diǎn)劃分到兩個(gè)點(diǎn)集中，并使得每條邊都是連接這兩個(gè)點(diǎn)集的邊匹配由圖中不相鄰的邊組成的集合最大匹配圖中匹配數(shù)最多的匹配完全匹配匹配邊的端點(diǎn)為所有圖中頂點(diǎn)二分圖的判定判定一個(gè)無向圖能否構(gòu)成二分圖算法：BFS，復(fù)雜度O(M)我們從任一點(diǎn)開始，令其在二分圖左邊，然后開始BFS，每次搜到的點(diǎn)放對(duì)面即可，直至所有點(diǎn)放完或出現(xiàn)矛盾正確性：對(duì)于每個(gè)連通量而言，一個(gè)點(diǎn)如果確定，其他點(diǎn)均確定，而這個(gè)點(diǎn)放左，放右實(shí)際上是對(duì)稱的方案例題1

NOIP2010，第三題關(guān)押罪犯將N個(gè)人分成兩組，其中M對(duì)人有Ci的不和諧值，如果有不和諧值為Ci的兩人在同一組，那么就會(huì)有Ci的不和諧值。要求找出一個(gè)分組方案，使得最大不和諧值最小。N<=20000M<=100000例題解答直接做不好下手由于要求最大值最小，即一個(gè)上界，所以我們可以二分這個(gè)上界那么我們就能確定哪些人不能在一組(不和諧值大于上界的)我們新建一張圖，把不能在一組的人之間連邊，此時(shí)我們只需判斷這個(gè)圖能否構(gòu)成二分圖即可。復(fù)雜度O(MlogM)，實(shí)現(xiàn)簡單例題2

HNOI2010Planar給定一個(gè)圖，此圖有一個(gè)包含所有頂點(diǎn)的環(huán)（可以認(rèn)為1-2-3-..-N-1）判斷此圖是否為平面圖平面圖若能將無向圖G畫在平面上，使得任意兩條邊不相交（可以在端點(diǎn)重合），則為平面圖T組數(shù)據(jù)T<=100N<=200M<=10000例題解答平面圖的判定不好做考慮問題特殊性1，每條邊其實(shí)有兩種畫法，在里面或在外面2，每條邊在里面或外面可能會(huì)與其他邊在里面或外面矛盾（如藍(lán)色與綠色矛盾）例題解答我們把每條邊在里面，在外面這兩種選擇看成兩個(gè)點(diǎn)，那么一共有2M個(gè)點(diǎn)用O(M^2)的時(shí)間判斷每兩個(gè)點(diǎn)是否矛盾如果矛盾就連條邊(保證自己選了，則矛盾的都不選，或自己不選，矛盾的必選)我們把每條邊在里面與在外面連條邊(保證兩個(gè)選擇只選一個(gè))那么如果這個(gè)圖能構(gòu)成二分圖，則原問題能夠成平面圖例題解答但是O(M^2)的判斷太慢考慮到平面圖的性質(zhì)：邊數(shù)與點(diǎn)數(shù)同階（在本題中可以3*N-6條邊作為上限，如果超過則直接判非平面圖）所以復(fù)雜度為O(N^2*T)網(wǎng)絡(luò)流現(xiàn)在想將一些物資從S運(yùn)抵T，必須經(jīng)過一些中轉(zhuǎn)站。連接中轉(zhuǎn)站的是公路，每條公路都有最大運(yùn)載量。每條弧代表一條公路，弧上的數(shù)表示該公路的最大運(yùn)載量。最多能將多少貨物從S運(yùn)抵T？4248473621STV1V2V3V4公路運(yùn)輸圖基本概念這是一個(gè)典型的網(wǎng)絡(luò)流模型。為了解答此題，我們先了解網(wǎng)絡(luò)流的有關(guān)定義和概念。若有向圖G=(V,E)滿足下列條件：有且僅有一個(gè)頂點(diǎn)S，它的入度為零，這個(gè)頂點(diǎn)S便稱為源點(diǎn)。有且僅有一個(gè)頂點(diǎn)T，它的出度為零這個(gè)頂點(diǎn)T便稱為匯點(diǎn)。每一條弧都有非負(fù)數(shù)，叫做該邊的容量。邊(vi,vj)的容量用cij表示。則稱之為網(wǎng)絡(luò)流圖，記為G=(V,E,C)可行流

對(duì)于網(wǎng)絡(luò)流圖G，每一條弧(i,j)都給定一個(gè)非負(fù)數(shù)fij，這一組數(shù)滿足下列三條件時(shí)稱為這網(wǎng)絡(luò)的可行流，用f表示它。1.流量限制

每一條弧(i,j)有fij≤Cij2.流量平衡 除源點(diǎn)S和匯點(diǎn)T以外的所有的點(diǎn)vi，恒有： ∑j(fij)=∑k(fjk)

該等式說明中間點(diǎn)vi的流量守恒，輸入與輸出量相等。3. 對(duì)于源點(diǎn)S和匯點(diǎn)T有， ∑i(fSi)=∑j(fjT)=V(f)

該等式說明源點(diǎn)流出量等于匯點(diǎn)流入量等于網(wǎng)絡(luò)流流量殘量網(wǎng)絡(luò)與增廣軌殘量網(wǎng)絡(luò)G’=(V,E,C),其中V,E與原網(wǎng)絡(luò)G相同，C為G中的容量-當(dāng)前流量（即剩余可流量）增廣軌就是一條S-T的不包含可流量為0的邊的路徑許多最大流算法都是通過不斷找增廣軌進(jìn)行增廣從而得到最大流定理：當(dāng)前流為最大流當(dāng)且僅當(dāng)無增廣軌一個(gè)重要的問題增廣一次，增加1的流量后無增廣軌了，而最大流卻不是1.我們可以走1-2-4和1-3-4得到2的流量反向弧剛才產(chǎn)生的問題在于沒有“后悔”的機(jī)會(huì)怎么解決？回溯搜索？復(fù)雜度上升至指數(shù)級(jí)。我們給每條邊增加一條反向弧即對(duì)于(i,j,c)我們?cè)黾舆?j,i,0)當(dāng)(i,j,c)被增廣了X的流量后，我們把反向弧的可流量增加X割切將所有點(diǎn)劃分為兩個(gè)點(diǎn)集。其中S和T在不同點(diǎn)集割的容量為兩點(diǎn)集之間的邊的容量和右圖割容量：8+4+4+1=17最大流流量=最小割容量引理:對(duì)于任一可行流F和任一割K，均有

當(dāng)所有割邊滿流時(shí)等號(hào)設(shè)F*為最大流，P*為最小割我們找到一個(gè)割集P由引理得對(duì)于之間的邊必然滿流且由割與最小割的關(guān)系所以最大流算法直接找增廣軌類似搜索，效率低采用分層思想Dinic算法BFS建立層次圖根據(jù)層次圖用DFS找增廣軌增廣，返回第一步1，建立層次圖對(duì)網(wǎng)絡(luò)進(jìn)行一次BFS每條邊要求要有可流量才能走S標(biāo)號(hào)1A->B，B的標(biāo)號(hào)為A的標(biāo)號(hào)+1復(fù)雜度O(M)2，Dfs找增廣軌Dfs中走的邊(a,b)要求有可流量且a標(biāo)號(hào)+1=b標(biāo)號(hào)層次圖中最多找m次增廣路每次在dfs中最多前進(jìn)n次，花費(fèi)O(n)每次修改流量花費(fèi)O(n)一次Dfs復(fù)雜度為O(m*n)二、Dinicabdcef10551055源匯棧abcde5500后退到原路徑中從源點(diǎn)能夠到達(dá)的最遠(yuǎn)點(diǎn)f一次Dfs，多次增廣！3，增廣對(duì)于棧中節(jié)點(diǎn)（即增廣軌），找出最小可流量min對(duì)增廣軌上每條邊的可流量減去min，每條邊的反向弧可流量增加min小結(jié)可以證明層次圖中的層次嚴(yán)格單調(diào)遞增，所以最多建N次循環(huán)N次BFS建立層次圖O(M)根據(jù)層次圖用DFS找增廣軌O(N*M)增廣，返回第一步O(N)復(fù)雜度為O(N^2*M)二分圖的最大匹配算法一：網(wǎng)絡(luò)流算法二：匈牙利算法算法三：Hopcroft-Karp算法網(wǎng)絡(luò)流算法解二分圖最大匹配對(duì)于二分圖G新建源點(diǎn)S，匯點(diǎn)TS連向左邊所有點(diǎn)，容量為1原圖所有邊容量為1右邊所有點(diǎn)連向T，容量為1對(duì)此網(wǎng)絡(luò)求最大流，最大流流量即為最大匹配數(shù)。匈牙利算法依然是找增廣軌的思想循環(huán)每個(gè)左邊點(diǎn)以此點(diǎn)為起點(diǎn)找增廣軌如果找到則增廣循環(huán)N個(gè)點(diǎn)，每次找增廣軌最多要找M次復(fù)雜度O(N*M)匈牙利算法偽代碼FunctionFind(i):boolean循環(huán)每個(gè)i鄰接的點(diǎn)jB[j]為假//B數(shù)組記錄每一輪右邊每個(gè)點(diǎn)是否找過，避免重復(fù)B[j]:=trueL[j]為0或者Find(L[j])為真//L數(shù)組記錄右邊每點(diǎn)匹配的左邊點(diǎn)L[j]:=I,find:=true,exit；//找到就退出，返回真Find:=false;//沒找到EndFunction主程序ForI:=1~NFillchar(B,0,sizeof(B))Iffind(i)theninc(Ans);Hopcroft-Karp算法借用Dinic分層思想每次對(duì)二分圖分層(把二分圖看做網(wǎng)絡(luò))再用匈牙利算法，但是每次只走a標(biāo)號(hào)+1=b標(biāo)號(hào)的邊可以證明最多進(jìn)行次分層每次用O(M)的時(shí)間找增廣軌復(fù)雜度目前已知的最快二分圖匹配算法小結(jié)時(shí)間復(fù)雜度代碼長度思維難度網(wǎng)絡(luò)流算法O(N2*M)較長較低匈牙利算法O(N*M)短低Hopcroft-Karp算法O(N0.5*M)中等中等由于匈牙利算法簡單好寫，并且實(shí)際表現(xiàn)非常優(yōu)秀，所以推薦優(yōu)先選擇匈牙利算法。例題

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

Wall草地

Grass

空地

Empty墻

Wall草地

Grass

空地

Empty【模型一】在問題的原型中，草地，墻這些信息不是我們所關(guān)心的，我們關(guān)心的只是空地和空地之間的聯(lián)系。因此，我們很自然想到了下面這種簡單的模型：以空地為頂點(diǎn)，有沖突的空地間連邊，我們可以得到右邊的這個(gè)圖：問題的求解目標(biāo)是尋求圖G的最大獨(dú)立集，即求G的獨(dú)立數(shù)α(G)。一般圖的α(G)是很難計(jì)算的。

獨(dú)立集是原圖點(diǎn)集的一個(gè)子集，其中任意兩點(diǎn)之間沒有邊。顯然這一模型不是屬于一些特殊的圖，給我們?cè)O(shè)計(jì)算法帶來很大的麻煩。【模型二】我們將每一行，每一列被墻隔開，且包含空地的連續(xù)區(qū)域稱作“塊”。顯然，在一個(gè)塊之中，最多只能放一個(gè)機(jī)器人。我們把水平方向的這些塊編上號(hào)；同樣，把豎直方向的塊也編上號(hào)。

123451234水平方向的塊編號(hào)豎直方向的塊編號(hào)把每個(gè)橫向塊看作X部的點(diǎn)，豎向塊看作Y部的點(diǎn)，若兩個(gè)塊有公共的空地，則在它們之間連邊。于是，問題轉(zhuǎn)化成這樣的一個(gè)二分圖：由于每條邊表示一個(gè)空地，有沖突的空地之間必有公共頂點(diǎn)，所以問題轉(zhuǎn)化為二分圖的最大匹配問題。

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

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輛車，則加一條弧I

N+J，容量為1，表示兩輛四驅(qū)車最多只能交手一次；

4、增加一個(gè)源點(diǎn)S，S與1到N中的每一個(gè)結(jié)點(diǎn)I都連一條弧S

I，容量為阿P的第I輛車的壽命；

5、增加一個(gè)匯點(diǎn)T，N+1到2N中的每一個(gè)結(jié)點(diǎn)N+J到T都連一條弧N+J

T，容量為阿Q的第J輛車的壽命；

6、再增加一個(gè)源點(diǎn)S2，加一條弧S2

S，容量為M，表示最多M場分站賽。構(gòu)圖普通算法：保存流量與容量就需要（2N+3）*（2N+3）*2Bits優(yōu)化：總共只有四類?。?、S2

S2、S

I(i∈1..N)3、I

J(i∈1..N，j∈N+1..2N)4、JT(j∈N+1..2N)

最多也不過1+N+N+N*N=（N+1）*（N+1）條弧

S2這個(gè)源點(diǎn)與S2

S這條弧都可以不要，只需規(guī)定最多擴(kuò)展M次流量即可馬控制棋盤問題已知n*m的棋盤，其中一些格子有障礙物?，F(xiàn)要在棋盤上無障礙物的格子中布置一些馬，每只馬可以控制兩個(gè)格子：一個(gè)是它所在的格子，另一個(gè)是它通過一步可以跳到的格子。馬一步可以跳到的格子如下所示：現(xiàn)在的問題是：至少要放多少只馬才能將所有無障礙物的格子控制？馬分析我們按照如下方法把棋盤染色：容易看出，若馬放在黑色格子上，它控制的另外一個(gè)格子必然是白色的；同樣，若馬放在白色