[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，把幾個比較模糊的地方給釐清。