独立博客: 哲学与程序

哲学与程序

Algorithm@POJ2989题解

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位的数来表示集合,使用位操作加以优化。

posted on 2011-01-07 17:48 哲学与程序 阅读(355) 评论(0)  编辑 收藏 引用 所属分类: Algorithm


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

公告

欢迎访问 http://zhexue.sinaapp.com

常用链接

随笔分类(37)

随笔档案(41)

Algorithm

最新随笔

搜索

最新评论

独立博客: 哲学与程序