acmicpc暑期集訓講座二分圖匹配-資料下載頁
2024-10-12 16:23本頁面
【導讀】一個公司有n個工作崗位空缺，每個崗位空。缺需要有一定資格的人來填補?，F(xiàn)在已知每個人所能勝任的若干工作，求。這m個人最多可以填補幾個工作崗位。一個圖的點，可以分割成兩個集合X和Y. 在集合內(nèi)部沒有邊。任何一條邊的兩個端點都分屬不同的集合。匹配的一般定義：匹配是二分圖所有邊的。現(xiàn)在，工作分配問題變成了求一個二分圖。二分匹配的經(jīng)典算法：。交錯鏈（增廣路）。選，未選，已選…幾個重要的性質(zhì)：。匈牙利算法的思路就是：不停地在一個二。分圖中尋找交錯鏈，直到找不到為止。尋找交錯鏈可以用BFS或DFS，其中BFS效。率很高，但實現(xiàn)較復雜。2，如果在右邊找到一個未被匹配的點，則。相匹配的那個點出發(fā)在右邊找其它的點，可以證明，對于每一個左邊的點最多進行。所以總的復雜度是O. 在一個m行n列的棋盤上，有些點被禁止，將棋盤染成黑白二色，點之間的二分匹配，F(xiàn)ZU-1467(數(shù)據(jù)范圍較大，必須用鄰接表實。二分圖匹配是一個比較難的內(nèi)容，如果不
【正文】 E條邊的二分圖 ?每一次 BFS的復雜度為 O(E) ?可以證明，對于每一個左邊的點最多進行一次 BFS就可以找到一個最大匹配 ?所以總的復雜度是 O(VE) 經(jīng)典問題 —— 棋盤覆蓋 ?在一個 m行 n列的棋盤上，有些點被禁止，問能否用 1x2的多米諾骨牌覆蓋其他位置？ ?如果不能全部覆蓋，則最多可以覆蓋多少個小格？ 經(jīng)典問題 —— 棋盤覆蓋 ? FZU1467 與這個問題幾乎一樣 ?解決思路： 先給棋盤染色！ 經(jīng)典問題 —— 棋盤覆蓋 ? 將棋盤染成黑白二色，則：任意一個多米諾骨牌必定會覆蓋一個白色的格子和一個黑色的格子！ ? 問題變成了黑點與白點之間的二分匹配，相鄰的點之間有一條邊。 作業(yè) ? TOJ1050 ? FZU1467(數(shù)據(jù)范圍較大，必須用鄰接表實現(xiàn) ) ?二分圖匹配是一個比較難的內(nèi)容，如果不能深入了解算法，可以先搞清楚它可以解決哪些問題，遇到此類問題只要套上模板就可以 AC
教學課件相關(guān)推薦
鄂ICP備17016276號-1