※ 引述《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 来解

两位的讨论已经超出小弟的理解范围了=。=所以网络流的max flow解法大致上思路是怎样的呢？

max flow太复杂了 这题应该可以greedy吧总是挑degree最小的位置先匹配 这样不行吗?任何一种最好的匹配方式 总是有某个地方可以转成degree=1

这图还是 planar 所以 maximum matching 应该可以更快吧..

楼上有找到相关资料吗？

http://courses.csail.mit.edu/6.889/fall11/lectures/但是应该是纯理论方法..

这连结是planar，楼上有bipartite planar的资料吗？