二分圖(匈牙利,km算法詳解)-wenkub.com
2025-02-16 03:35 本頁(yè)面
【正文】 ? 最?。? ? 看一道例題： PKU2195 PKU2195 題意： 有 N個(gè)人跟 N個(gè)房子 ,每個(gè)人跟房子都有一定的距離 , 現(xiàn)在要讓這 N個(gè)人全部回到 N個(gè)房子里面去 ,要求所 有人回去的距離最短 . 現(xiàn)在我們假設(shè)要求的是最大距離 .那么就是求最大權(quán) 匹配 . 下面我們先介紹一下 KM算法 KM算法 ? 基本概念：可行頂標(biāo)和相等子圖 ? 可行頂標(biāo)： L是一個(gè)關(guān)于結(jié)點(diǎn)的函數(shù)， L(x)是頂點(diǎn) x對(duì)應(yīng)的頂標(biāo)值。 ? 二分圖的每條邊帶有權(quán)值。對(duì)于傘兵的起始降落點(diǎn)不做限制。,如果有邊 ij，則在二分圖中引入邊 ij39。 如 : 3 4 1 1 1 3 2 2 3 2 輸出為 : 花費(fèi)最小的彈藥數(shù) PKU3041 對(duì)于上面那個(gè)數(shù)據(jù)我們可以用下面的表示 ,0表示無(wú)障礙物 ,1表示有 。 ? 2,假如節(jié)點(diǎn) u它邊上的另一個(gè)節(jié)點(diǎn) v已經(jīng)匹配 ,那么就轉(zhuǎn)向跟v匹配的節(jié)點(diǎn) ,假設(shè)是 w,然后再對(duì) w重復(fù) 1,2的步驟 ,即尋找增廣路 . ? 3,假如我們?cè)?1,2步過程中找到一條增廣路 , 那么修改各自對(duì)應(yīng)的匹配點(diǎn) ,轉(zhuǎn)步驟 4,若無(wú)增廣路 , 則退出 . ? 4,匹配數(shù) +1。 1 2 3 4 5 6 假如我們用 xM數(shù)組表示左邊節(jié)點(diǎn)對(duì)其右邊節(jié)點(diǎn)的匹配 , yM表示右邊節(jié)點(diǎn)對(duì)其左邊節(jié)點(diǎn)的匹配 ,初始化為 1。 二分圖的最大匹配 ? 匈牙利算法（時(shí)間復(fù)雜度 O(nm)） ? 其思想是用寬度優(yōu)先搜索來(lái)找增廣路徑（和floodfill算法類似 ? 轉(zhuǎn)化為單位容量簡(jiǎn)單網(wǎng)絡(luò)的最大流問題 ? 在二分圖的基礎(chǔ)上，加入源點(diǎn) s和匯點(diǎn) t，讓 s與每個(gè) X結(jié)點(diǎn)連一條邊，每個(gè) Y結(jié)點(diǎn)和 t連一條邊，所有弧的容量為 1。所有的邊關(guān)聯(lián)的兩個(gè)頂點(diǎn)中，恰好一個(gè)屬于集合 X，一個(gè)屬于集合 Y。 1 2 3 4 5 6 二分圖的匹配： 給定一個(gè)二分圖 G， M為G邊集的一個(gè)子集，如果 M滿足當(dāng)中的任意兩條邊都不依附于同一個(gè)頂點(diǎn)，則稱 M是一個(gè)匹配。這樣，飽和弧就對(duì)應(yīng)著匹配邊。 現(xiàn)在重點(diǎn)看節(jié)點(diǎn) 3,當(dāng)尋找下一條邊時(shí) ,如圖中的藍(lán)邊 ,我們發(fā)現(xiàn)節(jié)點(diǎn) 6的 yM[6]=2。 最小點(diǎn)覆蓋 ? 最小覆蓋： 最小覆蓋要求用最少的點(diǎn)（Ｘ集合或Ｙ集合的都行）讓每條邊都至少和其中一個(gè)點(diǎn)關(guān)聯(lián)。 1 0 1 0 1 0 0 1 0 首先 ,我們利用行跟列做
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1