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

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

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

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

1.對于一個已有的匹配（可以為空匹配）可以通過更改交錯鏈上的邊來獲取更大的匹配

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