作者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/m.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