Bipartite Matching Basic & UVA10418 大冒險

說好的Bipartite Matching...難得學了一些基本又做了一些基本題目
當然要留個名...

話說所有理論/證明/寫法都是參考演算法筆記的, 這個神網真的幫了我很多
以下全部都是向未來的我的自白:

 To 未來的我:

基本要說的都可以在裡面找到了...這裡只留下一些讓"你"更易回憶/理解的思路...

首先 Bipartite Matching與General Matching的關係很深, 基本上General Matching
的算法 (雖然還未看)都是以Bipartite Matching的算法加以變通, 明了一就應該明了全部...

然後所有Matching的題目好像都可以用Flow相關的算法來解 (不肯定)...
可恨我也不會Flow..慢慢再學起吧...=.=

再來Matching的算法複雜度基本還是很高的...題目要求如果不太大 (~10^2 - 10^3?)
特徵相附的話, 很可能可以用Matching過的

Bipartite Matching的算法實作起來100%是DFS (相信General Matching也是)
不難寫, 但背後概念要很清楚...
另有一版本是BFS取代DFS, 複雜度更低但好像有點難寫....

Matching 問題以我暫時理解可以有3種: Max/Min Cardinality, Max/Min Weight, Perfect Matching
沒有Weight的情況下, Max Cardinality = Perfect, 有Weight的考慮則很多變化, 也不是這篇的主題 (其實是還不懂=.=)

所以這篇就是學基本中的基本: 沒有Weight的 Max. Cardinality Bipartite Matching
雖然是所有Matching中最簡單的, 出奇地很多題目都用得上, 攻利地說算是性價比高吧...

OKOK, 有點長氣...入正題吧..

理論 / 算法

Bipartite Matching基於一個理論: Augmenting Path Theorem (Berge's Theorem)

證明很勉強地理解了, 但不會記下的..."你"有興趣自己回演算法筆記看吧...

首先定義Augmenting Path (跟Flow 那個Augmenting Path不知有沒有關係?)

是一條兩個end points都是未匹配點的梅花間竹path

這類path的特性是: 把path上的邊逆轉, 匹配的變成非匹配 (and vice versa) 則總Matching Cardinality會+1

然後 Augmenting Path Theorem證明的是: 圖上任意一個不能作Augmenting Path起點的未匹配點, 把它移除, 剩下的圖仍能找到原圖其中一個Maximum Matching

這直接導出最簡單, 基本的Bipartite Matching算法: Augmenting Path Algorithm

設G={X,Y}  X跟Y是二分的兩組vertex,  隨便選X或Y都可以, 把它們全都當作未匹配點

然後一個個試著找Augmenting Path, 找到的話Cardinality就加1了, 同時該點會變成匹配點

如果找不到的話, By Augmenting Path Theorem, 我們移除它 (或者直接不管它)就好了

每個點要不變成匹配點, 要不直接不管, 都是Access一次而已
而當中找Augmenting Path的部分則是用一次DFS (或者用BFS, 如上面所說)

這個很重要, 直接簡單地分析了複雜度:  V次DFS的複雜度

DFS又視乎圖用什麼結構,  Matrix的話是O(V^2),  List的話是O(V+E) = O(E)

所以整個Augmenting Path Algorithm 是 O(V^3) 或者 O(VE)

基本題目

先來看幾說基本題目, 各自都有得益

UVA259, UVA10092

題目很直接的就會讓你聯想到Matching

然後這道題也有很多Bipartite Matching的特性...

就是建圖的麻煩!  很多時要自己想個簡易的方法給vertex一些id

才能用Augmenting Path Algorithm去解!

例如這道題, 題中的一些貌似vertex的東西可以重覆使用數次, 例如4次

建圖時真的要把它們當時4個分別不同id的vertex!

當初我做的時候, 我自作聰明, 沒用分開4個不同的node, 我用同一個node
讓他找4次Augmenting Path, 其實我到現在還是認為可行的...

test case好像也過的了, 不知怎的就給我WA

結果還是要乖乖把它們分開幾個不同的node才行...這個要記住

UVA10080

也很直接的一題, 就是建圖時計一下距離吧...

UVA10243

哇哇哇, 這題真的可以重點講一下

來頭不小的...可是某年ACM World Final.....的試機題目 (o:

但已經獲益良多了...

如果要說直接題意的話, 其實是求Tree 的Minimum Vertex Cover

老實說 我開頭是完全不明白關Bipartite Matching什麼事...

然後開始發現Tree一定是Bipartite Graph嘛....(所以也可以2-color的)

但...Vertex Cover跟Max. Matching有關係嗎?

用筆畫了畫, 不知怎的好像剛好答案都一樣, 就交了

竟然AC了....

百思不得其解之下, 跑去問Google了, TMD 竟然還真的有這樣的一條Theorem
König's theorem

"...an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs..."

FUCK...我記住了...

話說General Graph的 minimum vertex cover好像也跟maximum matching一樣的說...?

UVA10418 大冒險

這條真的另開一篇說都不過份...

我為了這題流了多少血汗....

現實來說, 這題是WA的, 但我不知羞恥地認為是UVA Judge的問題

在我看來應該是AC的了...

這篇來看為什麼我這樣認為...

先說一說題目, 題目的變態程度很不一般

因為是劉汝佳"白書"中的題目 (好似係)

題目的running time是30秒 =.=

明顯是告訴你 "量你也做不到"...

題意是這樣的:

Given 一個 m*n的棋盤, 棋盤上有 2*k + 1 隻棋子

k 隻是紅色的, k隻是綠色的,  1隻是金色的

它們初始狀態是放在某些格子上, 同一格可以放多於一隻棋子 (放全部也可以)

然後再選定 t 個格子, 每個格子有一個值叫 r
代表該格子內最後要放 r 隻棋子

所以 t 個格子的 r 總和一定是 2*k + 1

再來是棋盤每一格都有不同高度,  

紅色棋子只能平走或向上爬; 綠色棋子只能平走或向下爬; 金色則無限制地移動

每一步可以選任意一隻棋子向上,下,左,或右走一步 (不能出棋盤外)

由於這樣的限制下, 可能無solution, 所以玩家可以使用一種魔法

把棋上所有棋子換成任意一種permutation, 即把它們任意互換位置

好了, 問題是問, 要達成目標, 最少需要用多少次魔法呢?

只是要理解題目就已經有種吃屎的感覺了對吧?

好吧, 我要高興的是在進一步調查之前, 我的思路基本是正確的...

是要Binary Search + Bipartite Matching的了

先來說說思路跟解法

首先大約的想法是...如何建圖!

這個Bipartite的兩Group很明顯是棋子與 t 個格子了..

而由於有法術跟金色棋子, 基本上每隻棋子都可以去任何一個格子的, 差別在於用多少次魔法

那麼有沒有可能分別找每粒棋子到每個格子的 最少魔法使用數呢?

正確性又如何?

答案是可以的!

正確性建基於一個Observation: 使用魔法的時機, 是在於所有棋子都沒路走的時候!

所有棋子(不包括金色)都沒路走, 其實代表紅色不能再爬上, 綠色也不能再爬下...

解決方法有一個, 而且肯定是最好的, 因為只使用 1次魔法! 把紅綠互換! (各自都是k隻!)

互換後, 所有沒路的變成所有都有路了!

發現這點後, 再來看看建圖的部分, 可以用BFS類似找最短路徑的方法, 找出每隻棋子到每個目標格子的"最少魔法使用數" 這個數字再進一步當成 Bipartite Graph 的 edge weight!

給個例子吧,  假設棋子A 最少用3次魔法可以到目標, 棋子B則要用4次

Physical Meaning是這樣的: 棋子A跟B 各自走這條"最好路徑" (好 = 用最少魔法次數的路徑)

直到沒路, 使用1次魔法; 然後再走下去...重覆3次,  這時A已經到目標了, 而B 還需要多一次魔法

就是說 它們的頭3次是"重疊"的, 可以用3次魔法同時解決它們的困境

說到這兒, 又開始理解Augmenting Path Algorithm的實作時, 自然會想到

用Binary Search去估算 魔法的次數, 每次估算就用一次Augmenting Path Algorithm!

只是找Augmenting Path的時候, 如果edge weight 大於正在估算的數值則要ignore

(就是當沒有這條edge的意思), 這樣確保所有Augmenting Path都能以少於等於

估算數值的魔法次數達成

然後又會發現, 怎麼沒考慮金色棋子?  其實這時再考慮也不遲

以上分析在沒有金色棋子的情況下是絕對成立的, 那金色棋子改變了什麼呢?

最直接想到的是, 金色棋子可以以1次魔法 直接把任意1隻棋子送到任意目標!
實際上, 就是金色先到任意目標, 跟任意棋子互換, 金色自己再次走到任意目標即可

那麼情況產生變化了, 這樣首先發現, 最多只需要2*k 次魔法就可以了, Binary Search的上限!

然後在Binary Search中的Maximum Matching, 假設Cardinality不是2*k+1

就是有某些棋子不能以估算數值內的次數移動到目標了...

那麼自然就可以試試用金色幫助它們吧?
可以想成是: 金色原本去所有目標的weight都是0 , 如果幫助了1隻棋子, 則全部變成1..如此類推

最高可以去到估數算值

所以,  如果 2*k + 1 - #max matching <= 估算數值x  

仍然可以說是成功!  因為剩下的棋子可以全部以金色棋子幫助它們!

呼! 終於做完了!!! Test Case都過了!  為什麼都是WA!

一直WA!!

嗚啊...難得一條非水題....

我心有不甘, 於是上演了我自導自演的偵探日記

首先, 當然是Google了...

出奇的是, 由於這題是變態Asian出的題目, 網上resources非常非常的少

我最先找到的是知名的UVA 解說網站 Algorithmist

它的solution跟我的基本就是一樣, 而且它的test case我都過了...信心大增, 再交

還是WA

UVA Official Forum竟然也沒人問這條...

很絕望, 這時我找到這個Github 上面有一堆UVA題目的solution啊!!

當中也有UVA10418的, 高興死我了

我可以random generate一些input跟它的對比一下再debug了

我也真的這樣做了...結果都一樣, 應該沒問題的啊..!?

難道...難道是它的code也是WA的嗎?  我就這樣把Github上的code 直貼上judge

果然WA了...

這不正常啊...那個Github用家不太像這樣腦殘吧? 把WA的Code放上來陰人嗎?

於是我隨機選了其它數條問題的solution再放上judge, 全都AC了!

這更加奇怪了...這時我跑去UVA Official Forum 開了一個thread虛心求問

果然還是吃白果了

然後我還厚面皮的去StackOverflow問了

果然還是吃白果了, 還不知那個路人給了我一個負皮了 (本來還1-2個正皮的=.=)

然後我還試住找了一下劉汝佳的email 發了一個email給他 (o:

果然還是吃白果了

很絕望的情況下, 我又跑回去Github...

這時我在想, 有沒有機會找到這個Github的作者資料? 

於是我Google這個用家 Bruce3557

發現他在UVA的帳號叫"Monkey D. Luffy"!
而他的確曾經AC了這道UVA10418的!

事情更加奇怪了 我也無從入手了...

這時發現這傢伙在Codeforce上也有帳號啊...叫"bruce3557"

雖然2年沒上線了..我還是試住給他發了一個message

然後竟然今天他給我回覆了!!

我當然打了一大段文字感謝神, 還有請他幫忙verify一下他的code是否亦能AC?
但他沒再回覆了...

話說我也叫Peter神幫忙試了一下, 他也WA了..

然後Peter神給了我一個網站看UVA的Submit Status

發現很久都沒人AC了, 而最近試交這題的除了我跟Peter神

還有一個叫 BrianFry 的神人 (AC了4200多條問題) 也WA了

這個人我認得是UVA Official Forum的常客, 經常回報Bug或是什麼的

可能他看到我在UVA Official Forum 的另一個post吧...

總之事情的發展就是這樣了...我當自己AC了不過份吧? 當它的Judge錯了也不過份吧?
最低限度是太不負責任了吧...說一句"我們試過了, 完全沒問題啊柒頭" 我也會高興點的

再等等看事情的發展吧....(最主要是看Bruce本人在CF怎樣覆我了...)