PKU3041-Asteroids

題目：http://poj.org/problem?id=3041
給一個N*N的棋盤(500*500)，以及M個小行星的座標
現在Bessie有個武器，發射一次可以把一行或一列的小行星毀滅掉
問至少要發射幾次才能毀滅全部小行星？


程式碼：http://codepad.org/nvaHU4lN
和這題PKU2226頗為神似…？
我先看到了2226翻譯在筆記本上、打算慢慢想
結果在POJ訓練計畫中「二分圖的最大匹配」找到了3041，瞬間被捏爆了

糊裡糊塗AC做法是這樣的：
N條Row和N條Col相當於二分圖的兩側，共2N個節點
只要有一顆小行星(i,j)，就將代表row i和代表col j的節點連起來
接下來利用匈牙利算法求最大二分匹配、結束

發現這件事真的很傻眼，
想了老半天的2226-Muddy Fields莫名其妙正解了(傻眼again)
我當然不會甘願一道想那麼久的題目就這樣AC掉

========================

檢討這個做法為什麼可行的思路是這樣的：

1.選擇發射武器的方式有2N種，分別是在N條Row或是N條Col使用，
想像是2N個0,1邏輯閘、分別R1,R2,...,RN以及C1,C2,...,CN

2.因為每個小行星都要打到，當有小行星(i,j)，表示「Ri或Cj」必須選至少一個

3.考慮某條邊(某個條件)的時候，如果把Ri和Cj兩者皆選顯然不太明智，
能不能夠找出一個最小邊集E'，使得所有邊選中的節點不重複，
而且只要考慮這些邊就能求解原問題(從答案的結論反過來思考)

4.根據匈牙利算法中「沒有可增廣路就是最大匹配」，
我們說一種邊集E'選取以後，
「存在增廣路即無法滿足題設」<=>「沒增廣路就是滿足」
這時隨意列一奇數邊組成的鏈狀路線：
○-○-○-○-○-○

一條可增廣路是長這樣的(「=」即匹配選中該邊，「●」即在邏輯閘上設on)
○-○=●-○=●-○

於是最左邊那條邊就有不滿足的危險，如果將可增廣路增廣以後變成：
●=○-●=○-●=○
於是滿足題設

========================

看了Discuss找到一個更棒的解釋 (POJ的Discuss真是非常重要的知識寶庫…)

「原問題可轉化成最小點覆蓋，在二分圖上最小點覆蓋=最大邊匹配」

所謂最小點覆蓋(cover)，就是在圖上選一些點、選中點相鄰的邊都會被蓋到
在所有邊都被蓋到的前提下讓選中的點最少

在這道問題裡，發射武器的位置就是點、小行星就是邊…

結論：不得不佩服證明最小點覆蓋的人，我要去K證明了