※ 引述《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的資料嗎？