作者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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1469276641.A.A4B.html
1F：推 vagrantlike: 两位的讨论已经超出小弟的理解范围了=。= 07/23 22:43
2F：→ vagrantlike: 所以网路流的max flow解法大致上思路是怎样的呢？ 07/23 22:45
3F：推 DJWS: max flow太复杂了 这题应该可以greedy吧 07/24 07:13
4F：→ DJWS: 总是挑degree最小的位置先匹配 这样不行吗? 07/24 07:16
5F：推 DJWS: 任何一种最好的匹配方式 总是有某个地方可以转成degree=1 07/24 07:28
6F：推 FRAXIS: 这图还是 planar 所以 maximum matching 应该可以更快吧.. 07/24 10:27
7F：推 DJWS: 楼上有找到相关资料吗？ 07/24 10:31
9F：→ FRAXIS: 但是应该是纯理论方法.. 07/24 11:09
10F：推 DJWS: 这连结是planar，楼上有bipartite planar的资料吗？ 07/25 08:26