..

• 直接按题目给的边建图，求一次最大匹配，从而得到最小独立集。判断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