天津大學(xué)ACM ICPC暑期集訓(xùn)講座二分圖匹配

ACM/ICPC暑期集訓(xùn)講座

二分圖匹配cnhawk2007.7.25經(jīng)典問題——工作分配一個(gè)公司有n個(gè)工作崗位空缺，每個(gè)崗位空缺需要有一定資格的人來填補(bǔ)。現(xiàn)在有m個(gè)人申請(qǐng)這n個(gè)工作。由于每個(gè)人工作能力不同，所以不同的人能勝任不同的工作。現(xiàn)在已知每個(gè)人所能勝任的若干工作，求這m個(gè)人最多可以填補(bǔ)幾個(gè)工作崗位。每個(gè)人只能做一份工作，每個(gè)工作崗位也只需要一個(gè)人二分圖的一般表述一個(gè)圖的點(diǎn)，可以分割成兩個(gè)集合X和Y在集合內(nèi)部沒有邊任何一條邊的兩個(gè)端點(diǎn)都分屬不同的集合匹配在工作分配的問題中，我們給出一個(gè)可行的分配方案，就是一個(gè)匹配。如果這個(gè)匹配是最優(yōu)的（可以填補(bǔ)的工作崗位最多），就是最大匹配。匹配匹配的一般定義：匹配是二分圖所有邊的一個(gè)子集，在這個(gè)子集中任意兩條邊都沒有公共點(diǎn)。最大匹配：邊數(shù)最多的一個(gè)匹配*覆蓋的概念：與匹配相關(guān)的頂點(diǎn)集二分圖最大匹配問題現(xiàn)在，工作分配問題變成了求一個(gè)二分圖中最大匹配的問題。二分匹配的經(jīng)典算法：

匈牙利算法（Ford-Fulkerson算法的變形）基本概念左邊／右邊交錯(cuò)鏈（增廣路） 對(duì)于一個(gè)已有的匹配而言 從未被覆蓋的點(diǎn)出發(fā)，尋找一個(gè)交錯(cuò)鏈。 交錯(cuò)鏈長度為奇數(shù)，它上面的邊依次為：未選，已選，未選，已選…未選１２１２４３３４交錯(cuò)鏈１２１２４３３４１２１２４３３４交錯(cuò)鏈幾個(gè)重要的性質(zhì)：

1.對(duì)于一個(gè)已有的匹配（可以為空匹配）可以通過更改交錯(cuò)鏈上的邊來獲取更大的匹配

2.如果我們找到了一個(gè)匹配，并且再也找不到交錯(cuò)鏈了，那么這個(gè)匹配是最大匹配匈牙利算法匈牙利算法的思路就是：不停地在一個(gè)二分圖中尋找交錯(cuò)鏈，直到找不到為止。尋找交錯(cuò)鏈可以用BFS或DFS，其中BFS效率很高，但實(shí)現(xiàn)較復(fù)雜。尋找交錯(cuò)鏈的算法1，從左某一個(gè)未被匹配的點(diǎn)開始尋找，把所有與它相連的點(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ì)列尋找交錯(cuò)鏈對(duì)每一個(gè)左邊的沒有被匹配的點(diǎn)進(jìn)行BFS，如果在右邊直接找到一個(gè)點(diǎn)沒有被匹配，那么我們就可以增加一條匹配的邊１２１２４３３４１２尋找交錯(cuò)鏈對(duì)每一個(gè)左邊的沒有被匹配的點(diǎn)進(jìn)行BFS，如果在右邊直接找到一個(gè)點(diǎn)沒有被匹配，那么我們就可以增加一條匹配的邊１２１２４３３４１３尋找交錯(cuò)鏈對(duì)每一個(gè)左邊的沒有被匹配的點(diǎn)進(jìn)行BFS，如果在右邊直接找到一個(gè)點(diǎn)沒有被匹配，那么我們就可以增加一條匹配的邊１２１２４３３４24尋找交錯(cuò)鏈尋找交錯(cuò)鏈：如果在右邊找到一個(gè)已經(jīng)被匹配了的點(diǎn)，則看看它是與左邊的哪個(gè)點(diǎn)相匹配的，從相匹配的那個(gè)點(diǎn)出發(fā)在右邊找其它的點(diǎn)，把它們加入隊(duì)列１２１２４３３４２４尋找交錯(cuò)鏈１２１２４３３４尋找交錯(cuò)鏈的算法1，從左某一個(gè)未被匹配的點(diǎn)開始尋找，把所有與它相連的點(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ì)列代碼（模板）Bipartite.cpp二分圖匹配（鄰接矩陣表示）鄰接表的圖需要修改一下復(fù)雜度分析對(duì)于一個(gè)有V個(gè)點(diǎn)，E條邊的二分圖每一次BFS的復(fù)雜度為O(E)可以證明，對(duì)于每一個(gè)左邊的點(diǎn)最多進(jìn)行一次BFS就可以找到一個(gè)最大匹配所以總的復(fù)雜度是O(VE)經(jīng)典問題——棋盤覆蓋在一個(gè)m行n列的棋盤上，有些點(diǎn)被禁止，問能否用1x2的多米諾骨牌覆蓋其他位置？如果不能全部覆蓋，則最多可以覆蓋多少個(gè)小格？經(jīng)典問題——棋盤覆蓋FZU-1467與這個(gè)問題幾乎一樣/problem.php?pid=1467解決思路： 先給棋盤染色！經(jīng)典問題——棋盤覆蓋將棋盤染成黑白二色，則：任意一個(gè)多米諾骨牌必定會(huì)覆蓋一個(gè)白色的格子和一個(gè)黑色的格子！問題變成了黑點(diǎn)與白點(diǎn)之間的二分匹配，相鄰的點(diǎn)之間有一條邊。作業(yè)TOJ