本文關(guān)鍵詞：匈牙利算法，由筆耕文化傳播整理發(fā)布。

hdu1150 匈牙利算法

本文章已收錄于：

分類：

版權(quán)聲明：本文為博主原創(chuàng)文章，未經(jīng)博主允許不得轉(zhuǎn)載。

?pid=1150

圖的最小點(diǎn)覆蓋數(shù) = 圖的最大匹配數(shù)；

konig定理：二分圖的最小頂點(diǎn)覆蓋數(shù)等于最大匹配數(shù)。
證明：
比如最大匹配是M。為了求最少的點(diǎn)讓每條邊都至少和其中一個(gè)點(diǎn)關(guān)聯(lián)。
M個(gè)點(diǎn)是足夠的。就是說(shuō)他們覆蓋最大匹配的那M條邊后，假設(shè)有某邊e沒(méi)被覆蓋，那么把e加入后會(huì)得到一個(gè)更大的匹配，出現(xiàn)矛盾。
M個(gè)點(diǎn)是必需的。匹配的M條邊，由于他們兩兩無(wú)公共點(diǎn)，就是說(shuō)至少有M個(gè)點(diǎn)才能把他們覆蓋。

#include

  本文關(guān)鍵詞：匈牙利算法，，由筆耕文化傳播整理發(fā)布。