题目:
有个高中老师需要组织一些朋友出去旅游,但老师思想保守,总想着“烧死那对异性恋”,怕一些学生在旅途中萌生爱意。于是他决定确保带出去的任意两个学生至少满足一下一个条件:
身高相差大于40cm,性别相同,喜欢不同音乐类型,喜欢的体育比赛相同(这样很可能支持不同球队,然后就聊得不愉快了)
请据此挑选尽量多的学生。
输入:第一行为学生总数n(n<=500),一下n行每行描述一个学生,先是一个整数,表示身高(cm),然后是一个字符,表示性别(M/F),然后是一个字符串表示音乐风格,最后一个字符串表示喜欢的体育赛事(字符串长度不超过100,且不含空白符)
分析: 本题来自于NWERC 2005. 题目的模型是二分图的最大独立集,即选择尽量多的点,使得任意两个节点不相邻。而最大独立集和最小覆盖是互补的,因此答案就是节点总数减去最大匹配数。 这里简单介绍一下,覆盖集、独立集。
- 覆盖集:对于每条边,至少有一个点被选中;
- 独立集:对于每条边,至少有一个点不被选中。
这样,本题的建模方法是:将每个人看作一个节点,如果两个人4个条件都不满足,就连成一条无向边;这样问题就转换成这个图的最大独立集,由于每个人非男即女,这个图是一个二分图。