推 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. 當作沒看到。(這題很可能只需要簡單的貪心法,不需要搞這麼複雜。)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.74.236
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1469328987.A.52F.html
推 hcsoso: 不介意純理論方法的話可以做到 O(n log^3 n), 使用 07/24 12:16
→ hcsoso: multiple-source multiple-sink max flow on planar graph 07/24 12:16
→ hcsoso: 不然的話, 用 electric flow 可以做到 O(n^{10/7}) 07/24 12:17
→ hcsoso: 另外 Gaussian elimination 加上 nested dissection 可以 07/24 12:18
→ hcsoso: 做到 randomized O(n^w/2) <= O(n^1.19) 07/24 12:18
→ hcsoso: 這幾種方法全部都很難實作... 07/24 12:19
推 vagrantlike: 感謝各位強者的建議<..>來找找相關資料研究一下 07/24 18:29
→ DJWS: 一樓說的是planar,那麼有bipartitle planar的資料嗎? 07/25 08:27
→ yr: 我在想雖然圖是 planar ,但是轉成 bipartite 還是嗎? 07/25 09:46
推 hcsoso: 使用 msms max flow 本身就需要 bipartite, 把一側全當 s 07/25 11:36
→ hcsoso: ource 另一側全當 sink;如果你指的是 max flow 在 bipar 07/25 11:36
→ hcsoso: tite planar 上有無更好的演算法,我想沒有,因為 subdiv 07/25 11:36
→ hcsoso: ide 所有邊便可將任意圖轉為 bipartite 07/25 11:36
推 hcsoso: 這題可能的希望是在 unweighted grid 上有更好的演算法, 07/25 11:40
→ hcsoso: 不過我沒有什麼想法… 07/25 11:40
推 FRAXIS: 不知道 bounded degree graph 有沒有比較快的方法 07/25 12:22
→ DJWS: 我指的是 bipartite planar graph 求 matching 07/25 19:35
推 hcsoso: msms max flow 是我所知最快求 bipartite planar matching 07/26 00:23
→ hcsoso: 的方法了, 去掉 bipartite 連能不能做到 O(n polylog n) 07/26 00:24
→ hcsoso: 都是未知 07/26 00:24
→ DJWS: 那你知不知道平面圖最大流=最小割=對偶圖最短路徑? 07/26 06:47
推 FRAXIS: 可惜平面圖 max flow 沒辦法直接解 msms max flow 07/26 12:21
→ DJWS: 原來如此 07/26 18:00
→ DJWS: 上面那個連結是 O(n log^3 n) = O(n polylog n) ? 07/26 18:01
推 FRAXIS: 是的 但是是計算 bipartite planar maximum matching 07/26 21:31
→ FRAXIS: planar maximum matching 現在還沒有 O(n polylog n) 法 07/26 21:36
→ DJWS: 上面那連結沒有說到bipartite啊? 07/27 06:55
→ DJWS: 抱歉我會錯意了 / 我想找的正是 bpmm 的資料 07/27 07:03