acmicpc暑期集訓(xùn)講座二分圖匹配-文庫(kù)吧資料
2024-10-20 16:23本頁(yè)面
【正文】 的分配方案，就是一個(gè)匹配。由于每個(gè)人工作能力不同，所以不同的人能勝任不同的工作。ACM/ICPC暑期集訓(xùn)講座 二分圖匹配 hawk 經(jīng)典問(wèn)題 —— 工作分配 ?一個(gè)公司有 n個(gè)工作崗位空缺，每個(gè)崗位空缺需要有一定資格的人來(lái)填補(bǔ)?，F(xiàn)在有 m個(gè)人申請(qǐng)這 n個(gè)工作。 ?現(xiàn)在已知每個(gè)人所能勝任的若干工作，求這 m個(gè)人最多可以填補(bǔ)幾個(gè)工作崗位。如果這個(gè)匹配是最優(yōu)的（可以填補(bǔ)的工作崗位最多），就是最大匹配。 ?最大匹配：邊數(shù)最多的一個(gè)匹配 ? *覆蓋的概念：與匹配相關(guān)的頂點(diǎn)集 二分圖最大匹配問(wèn)題 ?現(xiàn)在，工作分配問(wèn)題變成了求一個(gè)二分圖中最大匹配的問(wèn)題。 交錯(cuò)鏈長(zhǎng)度為奇數(shù)，它上面的邊依次為：未選，已選，未選，已選 … 未選 １ ２ １ ２ ４ ３ ３ ４ 交錯(cuò)鏈 １ ２ １ ２ ４ ３ ３ ４ １ ２ １ ２ ４ ３ ３
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1