推 vagrantlike: 兩位的討論已經超出小弟的理解範圍了=。= 07/23 22:43
→ vagrantlike: 所以網路流的max flow解法大致上思路是怎樣的呢？ 07/23 22:45
以圖論/組合最佳化的觀點來看這題：
1. 這題是找 maximum cardinality matching。
　（每個格子各是一個node。凡是遇到兩個相同又相鄰的數字，就連一條edge。）
2. 因為棋盤是 bipartite graph （想像西洋棋盤的黑白格子），
所以這題是找 maximum cardinality bipartite matching。
3. mcbm 的其中一種解法是 maximum flow：
bipartite graph 一邊的所有點各自接上 source，另一邊的所有點各自接上sink，
　 然後跑 maximum flow ，就得到 mcbm。
4. 同時棋盤也是 planar graph，同時棋盤的 maximum degree = 4。
　 所以極可能有更加奇葩的演算法。
如果你不懂圖論/組合最佳化，有兩種主要的應對方式：
1. 想辦法自學。（這個學校不會教）
2. 當作沒看到。（這題很可能只需要簡單的貪心法，不需要搞這麼複雜。）

兩位的討論已經超出小弟的理解範圍了=。=所以網路流的max flow解法大致上思路是怎樣的呢？

不介意純理論方法的話可以做到 O(n log^3 n), 使用multiple-source multiple-sink max flow on planar graphhttp://cs.brown.edu/~pnk/publications/msms2.pdf不然的話, 用 electric flow 可以做到 O(n^{10/7})另外 Gaussian elimination 加上 nested dissection 可以做到 randomized O(n^w/2) <= O(n^1.19)這幾種方法全部都很難實作...

感謝各位強者的建議<..>來找找相關資料研究一下

一樓說的是planar，那麼有bipartitle planar的資料嗎？

我在想雖然圖是 planar ，但是轉成 bipartite 還是嗎？

使用 msms max flow 本身就需要 bipartite, 把一側全當 source 另一側全當 sink；如果你指的是 max flow 在 bipartite planar 上有無更好的演算法，我想沒有，因為 subdivide 所有邊便可將任意圖轉為 bipartite這題可能的希望是在 unweighted grid 上有更好的演算法，不過我沒有什麼想法…

不知道 bounded degree graph 有沒有比較快的方法

我指的是 bipartite planar graph 求 matching

msms max flow 是我所知最快求 bipartite planar matching的方法了, 去掉 bipartite 連能不能做到 O(n polylog n)都是未知

那你知不知道平面圖最大流=最小割=對偶圖最短路徑?

可惜平面圖 max flow 沒辦法直接解 msms max flow

原來如此上面那個連結是 O(n log^3 n) = O(n polylog n) ?

是的 但是是計算 bipartite planar maximum matchingplanar maximum matching 現在還沒有 O(n polylog n) 法

上面那連結沒有說到bipartite啊?抱歉我會錯意了 / 我想找的正是 bpmm 的資料