想看更多的解题报告: http://blog.csdn.net/wangjian8006/article/details/7870410
转载请注明出处:http://blog.csdn.net/wangjian8006
题目大意:给出你一个无向图,然后对其中的点去上色, 只能上黑色和白色,要求是黑色点不能相邻,问最多能上多少黑色的顶点
解题思路:
点独立集:设无向图G=<V,E>,顶点集合V'是V的子集,若V'中的任意两个顶点都不相邻,则称V'为G的点独立集
这题求的是最大独立集
当然,这题可以看做是图上色问题,直接爆搜
还有一个定理是最大独立集=补图的最大团
最大团=补图的最大独立集
hdu1530最大团
/* Memory 212K Time 16MS */ #include <iostream> using namespace std; #define MAXV 110 int n,m; int map[MAXV][MAXV],vis[MAXV],tmp[MAXV]; int ans,cnt; void dfs(int x){ int i; if(x>n){ for(i=1;i<=n;i++) tmp[i]=vis[i]; ans=cnt; return ; } int flag=1; for(i=1;i<x;i++){ if(vis[i] && map[x][i]){ flag=0; break; } } if(flag){ vis[x]=1,cnt++; dfs(x+1); cnt--,vis[x]=0; } if(cnt+n-x>ans){ vis[x]=0; dfs(x+1); } } int main(){ int a,b,i,flag; int Case; scanf("%d",&Case); while(Case--){ memset(map,0,sizeof(map)); scanf("%d%d",&n,&m); while(m--){ scanf("%d%d",&a,&b); map[a][b]=map[b][a]=1; } ans=cnt=0; dfs(1); printf("%d\n",ans); flag=0; for (i=1;i<=n;i++){ if(tmp[i]){ if(flag) printf(" "); printf("%d",i); flag=1; } } printf("\n"); } return 0; }