PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題]zerojudge競賽題目b841:104北二5.骨牌遊戲

看板Prob_Solve (計算數學 Problem Solving)作者 (...)時間8年前 (2016/07/24 10:56), 編輯推噓8(8推 0噓 21→)
留言29則, 5人參與, 最新討論串3/4 (看更多)
推
07/23 22:43,
兩位的討論已經超出小弟的理解範圍了=。=
07/23 22:43
→
07/23 22:45,
所以網路流的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
推
07/24 12:16, , 1F
不介意純理論方法的話可以做到 O(n log^3 n), 使用
07/24 12:16, 1F
→
07/24 12:16, , 2F
multiple-source multiple-sink max flow on planar graph
07/24 12:16, 2F
→
07/24 12:17, , 4F
不然的話, 用 electric flow 可以做到 O(n^{10/7})
07/24 12:17, 4F
→
07/24 12:18, , 5F
另外 Gaussian elimination 加上 nested dissection 可以
07/24 12:18, 5F
→
07/24 12:18, , 6F
做到 randomized O(n^w/2) <= O(n^1.19)
07/24 12:18, 6F
→
07/24 12:19, , 7F
這幾種方法全部都很難實作...
07/24 12:19, 7F
推
07/24 18:29, , 8F
感謝各位強者的建議<..>來找找相關資料研究一下
07/24 18:29, 8F
→
07/25 08:27, , 9F
一樓說的是planar，那麼有bipartitle planar的資料嗎？
07/25 08:27, 9F
→
07/25 09:46, , 10F
我在想雖然圖是 planar ，但是轉成 bipartite 還是嗎？
07/25 09:46, 10F
推
07/25 11:36, , 11F
使用 msms max flow 本身就需要 bipartite, 把一側全當 s
07/25 11:36, 11F
→
07/25 11:36, , 12F
ource 另一側全當 sink；如果你指的是 max flow 在 bipar
07/25 11:36, 12F
→
07/25 11:36, , 13F
tite planar 上有無更好的演算法，我想沒有，因為 subdiv
07/25 11:36, 13F
→
07/25 11:36, , 14F
ide 所有邊便可將任意圖轉為 bipartite
07/25 11:36, 14F
推
07/25 11:40, , 15F
這題可能的希望是在 unweighted grid 上有更好的演算法，
07/25 11:40, 15F
→
07/25 11:40, , 16F
不過我沒有什麼想法…
07/25 11:40, 16F
推
07/25 12:22, , 17F
不知道 bounded degree graph 有沒有比較快的方法
07/25 12:22, 17F
→
07/25 19:35, , 18F
我指的是 bipartite planar graph 求 matching
07/25 19:35, 18F
推
07/26 00:23, , 19F
msms max flow 是我所知最快求 bipartite planar matching
07/26 00:23, 19F
→
07/26 00:24, , 20F
的方法了, 去掉 bipartite 連能不能做到 O(n polylog n)
07/26 00:24, 20F
→
07/26 00:24, , 21F
都是未知
07/26 00:24, 21F
→
07/26 06:47, , 22F
那你知不知道平面圖最大流=最小割=對偶圖最短路徑?
07/26 06:47, 22F
推
07/26 12:21, , 23F
可惜平面圖 max flow 沒辦法直接解 msms max flow
07/26 12:21, 23F
→
07/26 18:00, , 24F
原來如此
07/26 18:00, 24F
→
07/26 18:01, , 25F
上面那個連結是 O(n log^3 n) = O(n polylog n) ?
07/26 18:01, 25F
推
07/26 21:31, , 26F
是的 但是是計算 bipartite planar maximum matching
07/26 21:31, 26F
→
07/26 21:36, , 27F
planar maximum matching 現在還沒有 O(n polylog n) 法
07/26 21:36, 27F
→
07/27 06:55, , 28F
上面那連結沒有說到bipartite啊?
07/27 06:55, 28F
→
07/27 07:03, , 29F
抱歉我會錯意了 / 我想找的正是 bpmm 的資料
07/27 07:03, 29F
‣ 更多 DJWS 的文章
文章代碼(AID): #1Nb2vRKl (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 DJWS 的文章
文章代碼(AID): #1Nb2vRKl (Prob_Solve)