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

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

看板Prob_Solve (計算數學 Problem Solving)作者 (Light be with you)時間8年前 (2016/07/23 20:24), 編輯推噓7(7推 0噓 3→)
留言10則, 3人參與, 最新討論串2/4 (看更多)
※ 引述《vagrantlike (【傑克】喵嗚)》之銘言： : → yr: 我的想法是，可以覆蓋的組數跟顏色少的格子一樣多，不知道這 07/23 11:44 : → yr: 想法正不正確 07/23 11:44 : → yr: 似乎可以用 Hall's theorem 來證明 07/23 12:12 : 推 FRAXIS: 你有沒有試著找找反例？ 07/23 12:13 啊！剛找到了一個反例 X XOX X: 5 個 X O: 4 個 O XO O 看起來還是要乖乖用 max flow 來解 -- Some people are born on third base and go through life thinking they hit a triple. - Barry Switzer -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 138.75.44.199 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1469276641.A.A4B.html
推
07/23 22:43, , 1F
兩位的討論已經超出小弟的理解範圍了=。=
07/23 22:43, 1F
→
07/23 22:45, , 2F
所以網路流的max flow解法大致上思路是怎樣的呢？
07/23 22:45, 2F
推
07/24 07:13, , 3F
max flow太複雜了 這題應該可以greedy吧
07/24 07:13, 3F
→
07/24 07:16, , 4F
總是挑degree最小的位置先匹配 這樣不行嗎?
07/24 07:16, 4F
推
07/24 07:28, , 5F
任何一種最好的匹配方式 總是有某個地方可以轉成degree=1
07/24 07:28, 5F
推
07/24 10:27, , 6F
這圖還是 planar 所以 maximum matching 應該可以更快吧..
07/24 10:27, 6F
推
07/24 10:31, , 7F
樓上有找到相關資料嗎？
07/24 10:31, 7F
→
07/24 11:09, , 9F
但是應該是純理論方法..
07/24 11:09, 9F
推
07/25 08:26, , 10F
這連結是planar，樓上有bipartite planar的資料嗎？
07/25 08:26, 10F
‣ 更多 yr 的文章
文章代碼(AID): #1Nas7XfB (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 yr 的文章
文章代碼(AID): #1Nas7XfB (Prob_Solve)