2014年10月21日 星期二
[UVA] 11439 Maximizing the ICPC
github: https://github.com/wilson100hong/UVAOJ/tree/master/Volume_114/11439
This problem is a combination of binary search + general graph matching. The binary search part is easy, you just search the max ICPC that makes graph completely matched. For general matching part, you can implement Edmond's algorithm. I found java version which is very clear, or you can refer my c++ version, based on other's website 演算法筆記.
I wish I have time in future to write down a walk-through for Edmond's implementation, introducing interesting parts of blossom contract / relax, which involves some nice tricks.
這一題是一個Binary Search + General Matching的組合題。把每個選手看作node,相對的ICPC看成是edge,要做的是尋找最大的ICPC值,使得圖完全匹配。Binary Search 的部份相當簡單,而General Matching的實作相當有挑戰性。
看了網路上一些素材,演算法筆記對graph matching深入簡出:核心便是Augmented Path,matching 算法即為尋找圖中所殘留的augmented path。而augmented path只有可能從偶點 (Even Node) 出發,所以這收斂了圖searching的複雜度,也是為什麼Bipartie Matching的實作簡單的原因。了解了這個之後,就可以理解Edmond's Algorithm -- 一種general matching的算法了。Edmond's algorithm的核心是Blossom -- 也就是當偶點與偶點有cross edge時,這兩個偶點與其Least Common Ancestor形成的一個cycle,這樣特殊的集合。Blossom的特性是其上的每一點都可以被當作偶點,包含之前為 奇點(Odd Node)的點!所以augmented path現在不只是從偶點上出發了,它也可以從在blossom的奇點出發。
然而理解跟實作是兩回事。Blossom的contract 與 relax 非常的tricky,常常要把node union起來,blossom中又包著blossom,代碼非常容易寫錯。我是參考演算法筆記的C++的版本,裡面對union的處理第一次看也是一頭霧水。反而,我認為這個java的實作相當清楚易讀,是我比較喜歡的版本。
有空的話希望可以深入go through 一下 Edmond的 implementation,把幾個比較模糊的地方給釐清。
訂閱:
文章 (Atom)