acmicpc暑期集訓(xùn)講座二分圖匹配(存儲(chǔ)版)
【正文】 問題，遇到此類問題只要套上模板就可以 AC 。 ?每個(gè)人只能做一份工作，每個(gè)工作崗位也只需要一個(gè)人 二分圖的一般表述 ?一個(gè)圖的點(diǎn)，可以分割成兩個(gè)集合 X和 Y ?在集合內(nèi)部沒有邊 ?任何一條邊的兩個(gè)端點(diǎn)都分屬不同的集合 匹配 ?在工作分配的問題中，我們給出一個(gè)可行的分配方案，就是一個(gè)匹配。 ?現(xiàn)在已知每個(gè)人所能勝任的若干工作，求這 m個(gè)人最多可以填補(bǔ)幾個(gè)工作崗位。 尋找交錯(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ò)鏈 ?對每一個(gè)左邊的沒有被匹配的點(diǎn)進(jìn)行BFS，如果在右邊直接找到一個(gè)點(diǎn)沒有被匹配，那么我們就可以增加一條匹配的邊 １ ２ １ ２ ４ ３
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1