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
小果子 阅读(788)
评论(0) 编辑 收藏 引用 所属分类:
Acm