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

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

2、分成兩組，其中M對人有Ci的不和諧值，如果有不和諧值為Ci的兩人在同一組，那么就會有Ci的不和諧值。n要求找出一個分組方案，使得最大不和諧值最小。nN=20000 M=100000例題解答n直接做不好下手n由于要求最大值最小最大值最小，即一個上界，所以我們可以二分這個上界n那么我們就能確定哪些人不能在一組(不和諧值大于上界的)n我們新建一張圖，把不能在一組的人之間連邊，此時我們只需判斷這個圖能否構(gòu)成二分圖即可。n復(fù)雜度O(MlogM)，實現(xiàn)簡單例題2HNOI 2010 Planarn給定一個圖，此圖有一個包含所有頂點(diǎn)的環(huán)（可以認(rèn)為1-2-3-.-N-1）n判斷此圖是否為平面圖n平面圖n若能將無

3、向圖G畫在平面上，使得任意兩條邊不相交（可以在端點(diǎn)重合），則為平面圖nT組數(shù)據(jù)nT=100 N=200 MB，B的標(biāo)號為A的標(biāo)號+1n復(fù)雜度O(M)2，Dfs找增廣軌nDfs中走的邊(a,b)要求有可流量n且a標(biāo)號+1=b標(biāo)號l層次圖中最多找m次增廣路l每次在dfs中最多前進(jìn)n次，花費(fèi)O(n)l每次修改流量花費(fèi)O(n)l一次Dfs復(fù)雜度為O(m*n)二、Dinicabdcef10551055源匯棧abcde5500后退到原路徑中從源點(diǎn)能夠到達(dá)的最遠(yuǎn)點(diǎn)f一次Dfs，多次增廣！3，增廣n對于棧中節(jié)點(diǎn)（即增廣軌），找出最小可流量minn對增廣軌上每條邊的可流量減去min，每條邊的反向弧可流量增加mi

4、n小結(jié)n可以證明層次圖中的層次嚴(yán)格單調(diào)遞增，所以最多建N次n循環(huán)N次nBFS建立層次圖O(M)n根據(jù)層次圖用DFS找增廣軌O(N*M)n增廣，返回第一步O(N)n復(fù)雜度為O(N2*M)二分圖的最大匹配n算法一：網(wǎng)絡(luò)流n算法二：匈牙利算法n算法三：Hopcroft-Karp算法網(wǎng)絡(luò)流算法解二分圖最大匹配n對于二分圖Gn新建源點(diǎn)S，匯點(diǎn)TnS連向左邊所有點(diǎn)，容量為1n原圖所有邊容量為1n右邊所有點(diǎn)連向T，容量為1n對此網(wǎng)絡(luò)求最大流，最大流流量即為最大匹配數(shù)。匈牙利算法n依然是找增廣軌的思想n循環(huán)每個左邊點(diǎn)n以此點(diǎn)為起點(diǎn)找增廣軌n如果找到則增廣n循環(huán)N個點(diǎn)，每次找增廣軌最多要找M次n復(fù)雜度O(N*M

5、)匈牙利算法偽代碼nFunction Find(i):booleann循環(huán)每個i鄰接的點(diǎn)jnBj為假 /B數(shù)組記錄每一輪右邊每個點(diǎn)是否找過，避免重復(fù)nBj:=truenLj為0或者Find(Lj)為真 /L數(shù)組記錄右邊每點(diǎn)匹配的左邊點(diǎn)nLj:=I ,find:=true,exit； /找到就退出，返回真nFind:=false; /沒找到nEnd Functionn主程序nFor I:=1NnFillchar(B,0,sizeof(B)nIf find(i) then inc(Ans);Hopcroft-Karp算法n借用Dinic分層思想n每次對二分圖分層(把二分圖看做網(wǎng)絡(luò))n再用匈牙利算法

6、，但是每次只走na標(biāo)號+1=b標(biāo)號的邊n可以證明最多進(jìn)行 次分層n每次用O(M)的時間找增廣軌n復(fù)雜度n目前已知的最快二分圖匹配算法N)*(MNO小結(jié)時間復(fù)雜度時間復(fù)雜度代碼長度代碼長度思維難度思維難度網(wǎng)絡(luò)流算法O(N2*M)較長較低匈牙利算法O(N*M)短低Hopcroft-Karp算法O(N0.5*M)中等中等由于匈牙利算法簡單好寫，并且實際表現(xiàn)非常優(yōu)秀，所以推薦優(yōu)先選擇匈牙利算法。例題 機(jī)器人布陣機(jī)器人布陣有一個N*M(N,M=50)的棋盤，棋盤的每一格是三種類型之一：空地、草地、墻。機(jī)器人只能放在空地上。在同一行或同一列的兩個機(jī)器人，若它們之間沒有墻，則它們可以互相攻擊。問給定的棋盤，

7、最多可以放置多少個機(jī)器人，使它們不能互相攻擊。墻 Wall草地 Grass 空地 Empty墻 Wall草地 Grass 空地 Empty【模型一】在問題的原型中，草地，墻這些信息不是我們所關(guān)心的，我們關(guān)心的只是空地和空地之間的聯(lián)系。因此，我們很自然想到了下面這種簡單的模型：以空地為頂點(diǎn)，有沖突的空地間連邊，我們可以得到右邊的這個圖 ：問題的求解目標(biāo)是尋求圖G的最大獨(dú)立集，即求G的獨(dú)立數(shù)(G)。一般圖的(G)是很難計算的。 獨(dú)立集是原圖點(diǎn)集的一個子集，其中任意兩點(diǎn)之間獨(dú)立集是原圖點(diǎn)集的一個子集，其中任意兩點(diǎn)之間沒有邊。沒有邊。顯然這一模型不是屬于一些特殊的圖，給我們設(shè)計算法帶來很大的麻煩?！灸?/p>

8、型二】我們將每一行，每一列被墻隔開，且包含空地的連續(xù)區(qū)域稱作“塊”。顯然，在一個塊之中，最多只能放一個機(jī)器人。我們把水平方向的這些塊編上號；同樣，把豎直方向的塊也編上號。 123451234水平方向的塊編號豎直方向的塊編號把每個橫向塊看作X部的點(diǎn)，豎向塊看作Y部的點(diǎn)，若兩個塊有公共的空地，則在它們之間連邊。于是，問題轉(zhuǎn)化成這樣的一個二分圖：由于每條邊表示一個空地，有沖突的空地之間必有公共頂點(diǎn)，所以問題轉(zhuǎn)化為二分圖的最大匹配問題。 阿阿P與阿與阿Q都是四驅(qū)車好手，他們各有都是四驅(qū)車好手，他們各有N輛四驅(qū)車。為了一比高下，他輛四驅(qū)車。為了一比高下，他們約好進(jìn)行一場比賽。們約好進(jìn)行一場比賽。 這次比

9、賽共有這次比賽共有M個分站賽，贏得分站賽場次多的獲得總冠軍。個分站賽，贏得分站賽場次多的獲得總冠軍。 每個分站賽中，兩人各選一輛自己的賽車比賽。分站賽的勝負(fù)大部分每個分站賽中，兩人各選一輛自己的賽車比賽。分站賽的勝負(fù)大部分取決于兩車的性能，但由于種種原因（如相互之間的干擾），性能并不取決于兩車的性能，但由于種種原因（如相互之間的干擾），性能并不是決定勝負(fù)的唯一指標(biāo)，有時會出現(xiàn)是決定勝負(fù)的唯一指標(biāo)，有時會出現(xiàn)A贏贏B、B贏贏C、C贏贏D、D又贏又贏A的局的局面。幸好有一種高智能機(jī)器，只要給定兩輛四驅(qū)車，就能立刻判斷誰會面。幸好有一種高智能機(jī)器，只要給定兩輛四驅(qū)車，就能立刻判斷誰會贏，在總比賽前它

10、就已經(jīng)把阿贏，在總比賽前它就已經(jīng)把阿p的每輛車與阿的每輛車與阿q的每輛車都兩兩測試過了，的每輛車都兩兩測試過了，并且還把輸贏表輸入了電腦。并且還把輸贏表輸入了電腦。 另外，由于比賽的磨損，每輛四驅(qū)車都有自己的壽命（即它們能參加另外，由于比賽的磨損，每輛四驅(qū)車都有自己的壽命（即它們能參加分站賽的場次），不同的四驅(qū)車壽命可能不同，但最多不會超過分站賽的場次），不同的四驅(qū)車壽命可能不同，但最多不會超過50場。場。兩輛四驅(qū)車最多只能交手一次。兩輛四驅(qū)車最多只能交手一次。 現(xiàn)給定現(xiàn)給定N、M（1=N=100，1=M=1000）、）、N*N的一個輸贏的一個輸贏表、每輛四驅(qū)車的壽命，并假設(shè)每次分站賽兩人都有

11、可選的賽車，請你表、每輛四驅(qū)車的壽命，并假設(shè)每次分站賽兩人都有可選的賽車，請你計算一下阿計算一下阿P最多能夠贏得多少個分站賽。最多能夠贏得多少個分站賽。例例 賽車問題賽車問題問題描述問題描述 1、建立N個點(diǎn)代表阿P的N輛車，分別以1到N標(biāo)號； 2、建立N個點(diǎn)代表阿Q的N輛車，分別以N+1到2N標(biāo)號； 3、如果阿P的第I輛車能夠跑贏阿Q的第J輛車，則加一條弧IN+J，容量為1，表示兩輛四驅(qū)車最多只能交手一次； 4、增加一個源點(diǎn)S，S與 1到N中的每一個結(jié)點(diǎn)I都連一條弧SI，容量為阿P的第I輛車的壽命； 5、增加一個匯點(diǎn)T，N+1到2N中的每一個結(jié)點(diǎn)N+J到T都連一條弧N+JT，容量為阿Q的第J輛

12、車的壽命； 6、再增加一個源點(diǎn)S2，加一條弧S2S，容量為M，表示最多M場分站賽 。構(gòu)構(gòu) 圖圖普通算法：保存流量與容量就需要（2N+3）*（2N+3）*2Bits 優(yōu)化：總共只有四類弧：1、S2S 2、SI(i1.N)3、IJ(i1.N，jN+1.2N) 4、 JT(jN+1.2N) 最多也不過1+N+N+N*N=（N+1）*（N+1）條弧 S2這個源點(diǎn)與S2S這條弧都可以不要，只需規(guī)定最多擴(kuò)展M次流量即可馬控制棋盤問題n已知n * m的棋盤，其中一些格子有障礙物。現(xiàn)要在棋盤上無障礙物的格子中布置一些馬，每只馬可以控制兩個格子：一個是它所在的格子，另一個是它通過一步可以跳到的格子。馬一步可以跳

13、到的格子如下所示：n現(xiàn)在的問題是：至少要放多少只馬才能將所有無障礙物的格子控制？馬分析 n我們按照如下方法把棋盤染色： n容易看出，若馬放在黑色格子上，它控制的另外一個格子必然是白色的容易看出，若馬放在黑色格子上，它控制的另外一個格子必然是白色的；同樣，若馬放在白色格子上，它控制的另外一個格子必然是黑色的。；同樣，若馬放在白色格子上，它控制的另外一個格子必然是黑色的。n將每個格子抽象成一個頂點(diǎn)，所有頂點(diǎn)的集合記為將每個格子抽象成一個頂點(diǎn)，所有頂點(diǎn)的集合記為V。把染成黑色的格。把染成黑色的格子所代表的頂點(diǎn)集記為子所代表的頂點(diǎn)集記為B，其余白色格子所代表頂點(diǎn)集記為，其余白色格子所代表頂點(diǎn)集記為W。n若馬能夠從格子若馬能夠從格子a一步跳到格子一步跳到格子b，就在頂點(diǎn)，就在頂點(diǎn)a、b之間添加一條邊之間添加一條邊n，將所有邊的集合記為，將所有邊的集合記為E。根據(jù)前面的分析可知。根據(jù)前面的分析可知a、 b必然分屬必然分屬W、B。n因此，因此，G = (W, B, E)是一個二部圖。是一個二部圖。算法n如果一只馬控制的兩個格子為a, b，我們可以看作是這只馬控制了以a, b為頂點(diǎn)的邊。故現(xiàn)在的問題是：從二部圖G = (W, B, E)中選取最少的邊，覆蓋所有的頂點(diǎn)。n這是一個典型的最小邊覆蓋問題。其算法如下：nstep 1. 求G = (W, B, E)的最大匹配M。nstep