hdu 1068 Girls and Boys (二分图的最大独立集,匈牙利算法)

2016年5月28日 0 作者 CrazyKK

hdu 1068题目链接
题意:有n个同学。。给出同学之间的 爱慕关系。。。选出一个集合使得集合中的人没有爱慕关系。问能选出的最大集合是多少。

思路:没有数据范围,差评!题意说得也不清楚。。由数据知道。。爱慕关系一定是相互的。。。

这道题实际上是二分图的最大独立集问题。

最大独立集问题: 在N个点的图G中选出m个点,使这m个点两两之间没有边.求m最大值

 

学到的一点是:对于二分图,可能并不能明显得分成两个不相交的集合,而是一个整体。(有左集合到又集合的边,同时有又集合到左集合的边,就是说每条边都是无相边。。?) 这其实等于把两个无向图叠加在了一起(从左指向右的和从又指向左的)

所以hungary得到的最大匹配数应该除以2,才是真正的最大匹配数。