作者DJWS (...)
看板Prob_Solve
标题Re: [问题]zerojudge竞赛题目b841:104北二5.骨牌游戏
时间Sun Jul 24 10:56:23 2016
1F：推 vagrantlike: 两位的讨论已经超出小弟的理解范围了=。= 07/23 22:43
2F：→ 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. 当作没看到。（这题很可能只需要简单的贪心法，不需要搞这麽复杂。）
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.250.74.236
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1469328987.A.52F.html
3F：推 hcsoso: 不介意纯理论方法的话可以做到 O(n log^3 n), 使用 07/24 12:16
4F：→ hcsoso: multiple-source multiple-sink max flow on planar graph 07/24 12:16
6F：→ hcsoso: 不然的话, 用 electric flow 可以做到 O(n^{10/7}) 07/24 12:17
7F：→ hcsoso: 另外 Gaussian elimination 加上 nested dissection 可以 07/24 12:18
8F：→ hcsoso: 做到 randomized O(n^w/2) <= O(n^1.19) 07/24 12:18
9F：→ hcsoso: 这几种方法全部都很难实作... 07/24 12:19
10F：推 vagrantlike: 感谢各位强者的建议<..>来找找相关资料研究一下 07/24 18:29
11F：→ DJWS: 一楼说的是planar，那麽有bipartitle planar的资料吗？ 07/25 08:27
12F：→ yr: 我在想虽然图是 planar ，但是转成 bipartite 还是吗？ 07/25 09:46
13F：推 hcsoso: 使用 msms max flow 本身就需要 bipartite, 把一侧全当 s 07/25 11:36
14F：→ hcsoso: ource 另一侧全当 sink；如果你指的是 max flow 在 bipar 07/25 11:36
15F：→ hcsoso: tite planar 上有无更好的演算法，我想没有，因为 subdiv 07/25 11:36
16F：→ hcsoso: ide 所有边便可将任意图转为 bipartite 07/25 11:36
17F：推 hcsoso: 这题可能的希望是在 unweighted grid 上有更好的演算法， 07/25 11:40
18F：→ hcsoso: 不过我没有什麽想法… 07/25 11:40
19F：推 FRAXIS: 不知道 bounded degree graph 有没有比较快的方法 07/25 12:22
20F：→ DJWS: 我指的是 bipartite planar graph 求 matching 07/25 19:35
21F：推 hcsoso: msms max flow 是我所知最快求 bipartite planar matching 07/26 00:23
22F：→ hcsoso: 的方法了, 去掉 bipartite 连能不能做到 O(n polylog n) 07/26 00:24
23F：→ hcsoso: 都是未知 07/26 00:24
24F：→ DJWS: 那你知不知道平面图最大流=最小割=对偶图最短路径? 07/26 06:47
25F：推 FRAXIS: 可惜平面图 max flow 没办法直接解 msms max flow 07/26 12:21
26F：→ DJWS: 原来如此 07/26 18:00
27F：→ DJWS: 上面那个连结是 O(n log^3 n) = O(n polylog n) ? 07/26 18:01
28F：推 FRAXIS: 是的 但是是计算 bipartite planar maximum matching 07/26 21:31
29F：→ FRAXIS: planar maximum matching 现在还没有 O(n polylog n) 法 07/26 21:36
30F：→ DJWS: 上面那连结没有说到bipartite啊? 07/27 06:55
31F：→ DJWS: 抱歉我会错意了 / 我想找的正是 bpmm 的资料 07/27 07:03