xiaoguozi's Blog
Pay it forword - 我并不觉的自豪,我所尝试的事情都失败了······习惯原本生活的人不容易改变,就算现状很糟,他们也很难改变,在过程中,他们还是放弃了······他们一放弃,大家就都是输家······让爱传出去,很困难,也无法预料,人们需要更细心的观察别人,要随时注意才能保护别人,因为他们未必知道自己要什么·····

http://acm.hdu.edu.cn/showproblem.php?pid=1530(赤裸裸的最大团)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1419

pku1419解析:
本题是给定一个无向图G,对顶点进行染色(0,1),使相邻的两个点不同时为1(黑色),因为n>=100,直接暴搜的话复杂度为2^100,(据说也能过,未尝试),换思路,因为相邻的点不能同时为1,所以只要找出最大的一个集合,使该集合内的点都没有边,集合内点的个数就是答案,就是求最大独立集...而最大独立集=G' 的最大团...所以转化为求最大团......

posted on 2008-07-31 13:03 小果子 阅读(786) 评论(0)  编辑 收藏 引用 所属分类: Acm

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