推 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 的资料