作者yr (Light be with you)
看板Prob_Solve
標題Re: [問題]zerojudge競賽題目b841:104北二5.骨牌遊戲
時間Sat Jul 23 20:23:58 2016
※ 引述《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
推 vagrantlike: 兩位的討論已經超出小弟的理解範圍了=。= 07/23 22:43
→ vagrantlike: 所以網路流的max flow解法大致上思路是怎樣的呢？ 07/23 22:45
推 DJWS: max flow太複雜了 這題應該可以greedy吧 07/24 07:13
→ DJWS: 總是挑degree最小的位置先匹配 這樣不行嗎? 07/24 07:16
推 DJWS: 任何一種最好的匹配方式 總是有某個地方可以轉成degree=1 07/24 07:28
推 FRAXIS: 這圖還是 planar 所以 maximum matching 應該可以更快吧.. 07/24 10:27
推 DJWS: 樓上有找到相關資料嗎？ 07/24 10:31
→ FRAXIS: 但是應該是純理論方法.. 07/24 11:09
推 DJWS: 這連結是planar，樓上有bipartite planar的資料嗎？ 07/25 08:26