談匈牙利算法 Hungarian Algorithm

匈牙利算法是小弟今天放學剛剛學會的一種算法，其實以前都略略聽過 ......

那是像匈牙利輕騎兵一樣，強得很的東西。

它可以用來解決二分圖模型的問題，包括部份網絡流問題 !

我看過幾個網頁，嘗試理解，

根據 匈牙利算法@百度，

匈牙利算法是無比抽象的東西，

增廣路徑、匹配M、集合M，just to name a few，我郁悶了。

再看看 匈牙利算法@維基，

雖然沒有文字解釋，但用心去解讀後，相信比較易去明白，

也明白了這個算法的運作很難只用文字表達......

建議看百度大概理解這算法是什麽，再看維基了解詳細運作。

算法輪廓 : 若P是圖G中一條連通兩個未匹配頂點的路徑，並且屬M的邊和不屬M的邊(即已匹配和待匹配的邊)在P上交替出現，則稱P為相對於M的一條增廣路徑。
(1) 置M為空
(2) 找出一條增廣路徑P，通過取反操作獲得更大的匹配M’代替M
(3) 重復(2)操作直到找不出增廣路徑為止

看不懂還是看 WIKI 的 pascal code 吧。

---------------------------------------

例題 :

1 : pku 1274 The Perfect Stall

問題是有 N 隻母牛，M個倉，每日，每隻牛只會去某幾個倉渣一單位奶。
當中一個倉只能容納一隻母牛，請問最多可以渣多少單位奶 ?

解法 : 把二分圖，左邊為母牛，右邊為倉，牛倉關係為頂點路徑，製成二分圖，
利用匈牙利算法便輕鬆可解決。
(用網絡流也可以做到)

2 : pku 3041 Asteroids

問題是有 N*N 的距陣，某些格子有小行星，
現在最強武器褶櫈，它可以剷除一行或一列的小行星，
問最少要多少最強武器才可以消滅所有小行星 ?

解法 : 非常巧妙地把題目的距陣和小行星化成二分圖，
左邊為行，右邊為列，行星出現為路徑。
再利用輕騎戰術便解決了。

解釋 : 對於每一行 (橫向的row)，都會盡量去選除一粒小行星，分 A,B,C 三個 CASES :
A : 如果選到而小行星不是該行最後一個小行星，即代表最強武器會水平發射擊中該行所有小行星;
B : 如果小行星是該行最後一個小行星，即代表該行前部份的小行星已被上方的最強武器射中，最強武器會垂直射中該列所有小行星。
C : 如果沒有小行星被選中，即所有小行星被之前的最強武器的垂直攻擊打中。

3 : pku 2239 Selecting Courses

和 3041 相似的題目

4 : pku 2446 Chessboard

5 : pku 1466 Girls and Boys

6 : pku 1325 Machine Schedule

7 : pku 1469 COURSES