说实话，真心觉得这个实在是一个模拟的题目一般，但是知识点却是图论当中的独立集。。。掌握知识点不牢固啊。。
题意就是一个配色方案，对于一条边而言，两端的顶点颜色不能够相同，尽可能的将颜色染为黑色。。求配色方案当中的黑色最多为多少，输出一个最佳配色方案中的黑色节点。。
View Code 1 #include<iostream> 2 #include<stdio.h> 3 using namespace std; 4 struct node 5 { 6 int end,next; 7 }edge[10002]; 8 int head[102],n,m,start,end,maxval,color[102]; 9 int answer[102]; 10 void dfs(int i,int j) 11 { 12 if(i>=n) 13 { 14 if(j>maxval) 15 { 16 maxval=j; 17 for(int i=1;i<=n;i++)answer[i]=color[i]; 18 } 19 return ; 20 } 21 color[i]=-1; 22 int end; 23 for(end=head[i];end!=-1;end=edge[end].next) 24 { 25 if(color[edge[end].end]==-1) 26 break; 27 } 28 if(end==-1)dfs(i+1,j+1); 29 30 color[i]=1; 31 dfs(i+1,j); 32 color[i]=0; 33 34 } 35 int main() 36 { 37 int t; 38 scanf("%d",&t); 39 while(t--) 40 { 41 scanf("%d%d",&n,&m); 42 for(int i=1;i<=n;i++)head[i]=-1; 43 for(int i=0,Count=0;i<m;i++) 44 { 45 scanf("%d%d",&start,&end); 46 edge[Count].end=end; 47 edge[Count].next=head[start]; 48 head[start]=Count++; 49 edge[Count].end=start; 50 edge[Count].next=head[end]; 51 head[end]=Count++; 52 } 53 maxval=0; 54 dfs(1,0); 55 printf("%d\n",maxval); 56 for(int i=1;i<=n;i++)if(answer[i]==-1)printf("%d ",i); 57 printf("\n"); 58 } 59 return 0; 60 } 61 62
转载于:https://www.cnblogs.com/nuoyan2010/archive/2012/09/01/2667120.html
