>   请告诉我大致思路及方法，谢谢。

• 求树的最大独立集是可以贪心,可是那个YES和NO该怎么判断,如果贪心 (2) pku_ghost 2007-08-14 14:55:56
• 求树的最大独立集是可以贪心,可是那个YES和NO该怎么判断,如果贪心 (2) pku_ghost 2007-08-14 14:55:56
  • 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
• 比赛的时候，DFS+贪心过的 (119) alpc62 2007-08-14 19:17:42
  • 总算是贪心过了 (3) pku_ghost 2007-08-15 14:08:58