..

• 2分图匹配。 (6) bluewind 2007-08-14 15:32:19
  • Re:2分图匹配。 (12) whitesea 2007-08-14 17:06:45
  • 请问你说的匹配是怎么搞,怎么建图 (2) pku_ghost 2007-08-14 21:08:42
    • 直接按题目给的边建图，求一次最大匹配，从而得到最小独立集。判断Yes,No,去掉匹配上任意的一边，再做一次匹配，如果去掉任意一边都可以达到原来最大匹配的值Yes,否则No (0) bluewind 2007-08-14 21:57:32
      • Re:这个方法不错,我去试试 (0) wlch4712 2007-08-15 09:56:28
      • 这样复杂度是不是有点高 (0) mmd 2007-08-15 11:43:14
        • n*m的匹配(m=n),最多n的枚举，总的就是n^3 (0) bluewind 2007-08-15 13:28:37
      • 二分图果然可以过 嘿嘿 (0) ecjtunh 2007-08-23 17:09:41
      • Re:直接按题目给的边建图，求一次最大匹配，从而得到最小独立集。判断Yes,No,去掉匹配上任意的一边，再做一次匹配，如果去掉任意一边都可以达到原来最大匹配的值Yes,否则No (42) shixinfei 2010-08-26 09:58:41
        • 可是实际情况确实如bluewind所说，与你的设想相反，我也没想太明白 (45) Tornado 2011-07-05 10:00:01