HDU 3829 Cat VS Dog (最大独立集)

动物园有不同种类的猫和狗,有p个小朋友去参观动物园,每个小朋友都有喜欢或讨厌的猫或狗,现在如何移除某些动物使得最多的小朋友只看到自己喜欢的动物。

从猫和狗身上不容易建图,从小朋友身上找突破点,如果两个小朋友喜欢和讨厌的动物有冲突那么说明这两个小朋友的利益是冲突的,无法共存,如果按照这个建图最后只要求最大独立集即可。

 

LEAVE A COMMENT