7-6 部落卫队问题 (20分)

背包问题，部落卫队问题，子集合问题是一样的，对于每一层（这里是每个村民）都有2种可能，要或者不要

原始部落byteland中的居民们为了争抢有限的资源，经常发生冲突。几乎每个居民都有它的仇敌。部落酋长为了组织一支保卫部落的队伍，希望从部落的居民中选出最多的居民入伍，并保证队伍中任何两个人都不是仇敌。

输入格式:

第一行两个正整数n和m，表示byteland部落中有n个居民，居民间有m个仇敌关系， 0<n<200, 0<m<6000。居民编号为1,2,…,n。接下来输入m行中，每行正整数u和v，表示居民u和居民v是仇敌。

输出格式:

输出部落卫队最佳组建方案中包含的居民人数。之后逐个输出卫队组成xi, 1<=i<=n, xi=0表示居民i不在卫队中，xi=1表示居民i在卫队中。

输入样例:

7 10
1 2
1 4
2 4
2 3
2 5
2 6
3 5
3 6
4 5
5 6

　　

输出样例:

3
1 0 1 0 0 0 1 

代码：

#include <bits/stdc++.h>
using namespace std;

int n; // 有 n 个居民
int m; // 有 m 个仇敌关系 
bool hate[300][300]={0}; // a[i][j] 表示 居民 i 对 居民 j 是否 仇恨 , 1表示有 
bool inTeam[300]={0}; // 居民i是否在卫队中 inTeam[i]=1 表示在卫队中，初始化为0 
bool BestRecord[300]={0};  
int BestCount = 0; 

int GetCount( bool inTeam[] )   // 遍历 inTeam 数组 ，计算该方案下  卫队的人数 
{
    int count=0;
    for(int i=1;i<=n;i++)
    {
        if(inTeam[i]) count++;
    }
    return count;
}

void record()  // 把 最好的方案记录下来 
{
    // 复制 inTeam 到 BestRecord
    for(int i=1;i<=n;i++)    
        BestRecord[i] = inTeam[i];
    return ;     
}

bool CanIn(int dep) // 第 dep 个村民能否进入卫队 （和已经进入卫队的人有没有冲突） 
{
    for(int i=1;i<=n;i++)
         if( hate[dep][i] && inTeam[i] )   return 0;// dep 对 i 有仇， 而且 i 在 卫队 
    return 1;
} 

void search(int dep)   // 确定 第 dep 个村民要不要进入卫队  
{

  // 遍历到了叶子节点 ，得到一种方案 ， 更新 BestCount 和 BestRecord ,返回 
  if( dep > n ) 
  {
      int count = GetCount(inTeam);
      if( count > BestCount ) 
      {
          BestCount = count ;
          record();
      }
      return ; 
  }    
  
     //  第 i 个村民进入卫队 
     if(CanIn(dep)) 
     {
     inTeam[dep]=1;  
     if( (GetCount(inTeam)+(n-dep)) > BestCount )  search(dep+1); // 讨论 第 i+1 村民进不进 
     inTeam[dep]=0;
     } 
     
     // 第i个村民不进入卫队
      search(dep+1);

    

  return ; 
} 



int main()
{
   cin>>n>>m;
   
   for(int i=0;i<m;i++) // 记录m个仇恨关系 
   {
      int x,y;
      cin>>x>>y;
      hate[x][y] = 1 ;
      hate[y][x] = 1 ; 
      // x 和 y 是仇恨关系 
   }    
   
   search(1); // 从居民1开始 
   
   cout<<GetCount(BestRecord)<<endl;
   
   for(int i=1;i<=n;i++)
   {
      cout<<BestRecord[i]<<" ";    
   } 
   
   return 0;
}