二分匹配匈牙利算法

1、二分匹配匈牙利算法第1頁(yè)，共22頁(yè)。經(jīng)典問(wèn)題工作分配一個(gè)公司有n個(gè)工作崗位空缺，每個(gè)崗位空缺需要有一定資格的人來(lái)填補(bǔ)?，F(xiàn)在有m個(gè)人申請(qǐng)這n個(gè)工作。由于每個(gè)人工作能力不同，所以不同的人能勝任不同的工作?，F(xiàn)在已知每個(gè)人所能勝任的若干工作，求這m個(gè)人最多可以填補(bǔ)幾個(gè)工作崗位。每個(gè)人只能做一份工作，每個(gè)工作崗位也只需要一個(gè)人第2頁(yè)，共22頁(yè)。二分圖的一般表述一個(gè)圖的點(diǎn)，可以分割成兩個(gè)集合X和Y在集合內(nèi)部沒(méi)有邊任何一條邊的兩個(gè)端點(diǎn)都分屬不同的集合第3頁(yè)，共22頁(yè)。匹配在工作分配的問(wèn)題中，我們給出一個(gè)可行的分配方案，就是一個(gè)匹配。如果這個(gè)匹配是最優(yōu)的（可以填補(bǔ)的工作崗位最多），就是最大匹配。第4頁(yè)，共22

2、頁(yè)。匹配匹配的一般定義：匹配是二分圖所有邊的一個(gè)子集，在這個(gè)子集中任意兩條邊都沒(méi)有公共點(diǎn)。最大匹配：邊數(shù)最多的一個(gè)匹配*覆蓋的概念：與匹配相關(guān)的頂點(diǎn)集第5頁(yè)，共22頁(yè)。二分圖最大匹配問(wèn)題現(xiàn)在，工作分配問(wèn)題變成了求一個(gè)二分圖中最大匹配的問(wèn)題。二分匹配的經(jīng)典算法：匈牙利算法（Ford-Fulkerson算法的變形）第6頁(yè)，共22頁(yè)?；靖拍钭筮呌疫吔诲e(cuò)鏈（增廣路）對(duì)于一個(gè)已有的匹配而言從未被覆蓋的點(diǎn)出發(fā)，尋找一個(gè)交錯(cuò)鏈。交錯(cuò)鏈長(zhǎng)度為奇數(shù)，它上面的邊依次為：未選，已選，未選，已選未選第7頁(yè)，共22頁(yè)。交錯(cuò)鏈第8頁(yè)，共22頁(yè)。交錯(cuò)鏈幾個(gè)重要的性質(zhì)：1.對(duì)于一個(gè)已有的匹配（可以為空匹配）可以通過(guò)更改交錯(cuò)

3、鏈上的邊來(lái)獲取更大的匹配2.如果我們找到了一個(gè)匹配，并且再也找不到交錯(cuò)鏈了，那么這個(gè)匹配是最大匹配第9頁(yè)，共22頁(yè)。匈牙利算法匈牙利算法的思路就是：不停地在一個(gè)二分圖中尋找交錯(cuò)鏈，直到找不到為止。尋找交錯(cuò)鏈可以用BFS或DFS，其中BFS效率很高，但實(shí)現(xiàn)較復(fù)雜。第10頁(yè)，共22頁(yè)。尋找交錯(cuò)鏈的算法1，從左某一個(gè)未被匹配的點(diǎn)開(kāi)始尋找，把所有與它相連的點(diǎn)加進(jìn)隊(duì)列2，如果在右邊找到一個(gè)未被匹配的點(diǎn)，則算法結(jié)束3，如果在右邊找到一個(gè)已經(jīng)被匹配了的點(diǎn)，則看看它是與左邊的那個(gè)點(diǎn)相匹配的，從相匹配的那個(gè)點(diǎn)出發(fā)在右邊找其它的點(diǎn)，把它們加入隊(duì)列第11頁(yè)，共22頁(yè)。尋找交錯(cuò)鏈對(duì)每一個(gè)左邊的沒(méi)有被匹配的點(diǎn)進(jìn)行BFS

4、，如果在右邊直接找到一個(gè)點(diǎn)沒(méi)有被匹配，那么我們就可以增加一條匹配的邊第12頁(yè)，共22頁(yè)。尋找交錯(cuò)鏈對(duì)每一個(gè)左邊的沒(méi)有被匹配的點(diǎn)進(jìn)行BFS，如果在右邊直接找到一個(gè)點(diǎn)沒(méi)有被匹配，那么我們就可以增加一條匹配的邊第13頁(yè)，共22頁(yè)。尋找交錯(cuò)鏈對(duì)每一個(gè)左邊的沒(méi)有被匹配的點(diǎn)進(jìn)行BFS，如果在右邊直接找到一個(gè)點(diǎn)沒(méi)有被匹配，那么我們就可以增加一條匹配的邊24第14頁(yè)，共22頁(yè)。尋找交錯(cuò)鏈尋找交錯(cuò)鏈：如果在右邊找到一個(gè)已經(jīng)被匹配了的點(diǎn)，則看看它是與左邊的哪個(gè)點(diǎn)相匹配的，從相匹配的那個(gè)點(diǎn)出發(fā)在右邊找其它的點(diǎn)，把它們加入隊(duì)列第15頁(yè)，共22頁(yè)。尋找交錯(cuò)鏈第16頁(yè)，共22頁(yè)。尋找交錯(cuò)鏈的算法1，從左某一個(gè)未被匹配的點(diǎn)

5、開(kāi)始尋找，把所有與它相連的點(diǎn)加進(jìn)隊(duì)列2，如果在右邊找到一個(gè)未被匹配的點(diǎn)，則算法結(jié)束3，如果在右邊找到一個(gè)已經(jīng)被匹配了的點(diǎn)，則看看它是與左邊的哪個(gè)點(diǎn)相匹配的，從相匹配的那個(gè)點(diǎn)出發(fā)在右邊找點(diǎn)，把它們加入隊(duì)列第17頁(yè)，共22頁(yè)。代碼（模板）Bipartite.cpp二分圖匹配（鄰接矩陣表示）鄰接表的圖需要修改一下第18頁(yè)，共22頁(yè)。復(fù)雜度分析對(duì)于一個(gè)有V個(gè)點(diǎn)，E條邊的二分圖每一次BFS的復(fù)雜度為O(E)可以證明，對(duì)于每一個(gè)左邊的點(diǎn)最多進(jìn)行一次BFS就可以找到一個(gè)最大匹配所以總的復(fù)雜度是O(VE)第19頁(yè)，共22頁(yè)。經(jīng)典問(wèn)題棋盤(pán)覆蓋在一個(gè)m行n列的棋盤(pán)上，有些點(diǎn)被禁止，問(wèn)能否用1x2的多米諾骨牌覆蓋其他位置？如果不能全部覆蓋，則最多可以覆蓋多少個(gè)小格？第20頁(yè)，共22頁(yè)。經(jīng)典問(wèn)題棋盤(pán)覆蓋FZU-1467 與這個(gè)問(wèn)題幾乎一樣/problem.php?pid=1467解決思路：先給棋盤(pán)染色！第21頁(yè)，共22頁(yè)。經(jīng)典問(wèn)題棋