> 左半边是 match, 右半边是 square
> 左右半图之间的连线表示 match 是否 对 square 有贡献
> 
> 初始时, 把已经因为缺失 match 而不存在的 square 从图中删除
> 
> 问题: 从左半图中找出最少的点, 要求这些点可以通过边到达右半图所有的点
> 
> 没想到详细的解法

• 好象是覆盖问题, 找到个介绍, 贪心是不行的, 也许可以用匹配解 (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