http://acm.pku.edu.cn/JudgeOnline/problem?id=2989大致题意:给定一个含有n个人的集合S,S中的每两人要么是朋友,要么不是朋友。假如,S的一个子集合S',S'中任意两个人都互为朋友,且{S-S'}中的任意一个人与S'中的某些人不是朋友,则称S'为maximal sets of friends。
求maximal sets of friends的数量,大于1000则输出"Too many maximal sets of friends.",否则输出数量。
解法:
经典解法搜索+减枝。按顺序枚举集合S的子集合,并在枚举子集合的过程中判断子集合是否是maximal sets of friends,鉴于n<128,故使用两个64位的数来表示集合,使用位操作加以优化。