acmicpc暑期集訓(xùn)講座二分圖匹配-預(yù)覽頁
【正文】 ?尋找交錯鏈可以用 BFS或 DFS，其中 BFS效率很高，但實現(xiàn)較復(fù)雜。 匹配 ?匹配的一般定義：匹配是二分圖所有邊的一個子集，在這個子集中任意兩條邊都沒有公共點。由于每個人工作能力不同，所以不同的人能勝任不同的工作?，F(xiàn)在有 m個人申請這 n個工作。如果這個匹配是最優(yōu)的（可以填補(bǔ)的工作崗位最多），就是最大匹配。 交錯鏈長度為奇數(shù)，它上面的邊依次為：未選，已選，未選，已選 … 未選 １ ２ １ ２ ４ ３ ３ ４ 交錯鏈 １ ２ １ ２ ４ ３ ３ ４ １ ２ １ ２ ４ ３ ３ ４ 交錯鏈 ?幾個重要的性質(zhì)： （可以為空匹配）可以通過更改交錯鏈上的邊來獲取更大的匹配 ，并且再也找不到交錯鏈了，那么這個匹配是最大匹配 匈牙利算法 ?匈牙利算法的思路就是：不停地在一個二分圖中尋找交錯鏈，直到找不到
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1