将边与正方形都视为结点，看成二分图(还是叫二部图？偶不知道) 
然后在边所构成的结点集合中求最小割，转化为简单的图论问题.

• 求最小割, 一般要用最大流了, 问题是: 用最少的边破坏所有的正方形, 怎么理解,对应 (68) sunmoonstar 2006-05-16 13:15:07
• 好象有点匹配的意思 (153) sunmoonstar 2006-05-16 13:31:08
  • 感觉这个应该是 npc (169) sunmoonstar 2006-05-16 13:39:43
    • 就是一个n-sat (0) xfxyjwf 2006-05-16 13:43:42
      • 只能 search 了 (0) sunmoonstar 2006-05-16 13:53:45
  • 支配集吧 (169) frkstyc 2006-05-16 13:50:32
    • 好象是覆盖问题, 找到个介绍, 贪心是不行的, 也许可以用匹配解 (1654) sunmoonstar 2006-05-16 13:53:25
    • 恩,应该是支配集,我错了 (0) sunmoonstar 2006-05-16 13:55:11
    • 终于回归到经典模型, 基本理解 (0) sunmoonstar 2006-05-16 14:28:49
      • 但现在的问题是dominating set problem是npc (0) gniuxiao 2007-01-04 14:39:11
• 由此想到了一个剪枝: 如果一个 match 对 square 的贡献集合, 包含于另一个 match 的贡献集合, 就不用考虑了 (68) sunmoonstar 2006-05-16 13:35:05
  • 加了个剪枝, 结果剪枝所消耗的时间代价比它减少的搜索代价大得多..... (0) sunmoonstar 2006-05-17 21:12:25
    • ft,把数组改成 bitset 居然 ac 了, 算法一点没变, 如果加上 4 0, 5 0, 这两组数据就铁定过不去 (0) sunmoonstar 2006-05-17 21:16:26