uva 11825 巧妙地子集枚举方法

题目大意，有n台服务器，有n种服务，每台服务器都运行着所有的服务，一台服务器可以被攻击一次其中的一种服务，当你选择攻击某台服务器的某个服务时，与他相邻的服务器上的同种的服务也会被攻击，当某种服务在所有的服务器上都不再运行时，我们称消灭了一种服务，求黑客最多消灭几种服务。

n最大16，我们容易想到利用二进制表示已经攻击过的电脑，f(S)=MAX{f(S),f(S0^S)+1 | if(S0是S的子集&&S0攻击后可以覆盖全部的电脑)}

接下来的问题是如何判断某个电脑集合可以攻击到的范围，我们不妨用P[i]表示攻击第i个电脑后受到影响的所有电脑的集合，cover[i]表示攻击i集合里的全部电脑后受到影响的所有电脑的集合。对于子集的枚举有一种巧妙地方法:

for(int S0=S;S0;S0=(S0-1)&S); //其中，S表示原集合，S0为他的子集

当上面的问题都解决之后就好办了，

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int P[25],cover[1<<16],f[1<<16];
 4 int main()
 5 {
 6     int N,m,i,j,k=0,x;
 7     while(cin>>N&&N){
 8         memset(P,0,sizeof(P));
 9         memset(cover,0,sizeof(cover));
10         memset(f,0,sizeof(f));
11         for(i=0;i<N;++i)
12         {
13             P[i]|=(1<<i);
14             scanf("%d",&m);
15             while(m--){
16                 scanf("%d",&x);
17                 P[i]|=(1<<x);
18             }
19         }
20        for(i=1;i<(1<<N);++i)
21        {
22            for(j=0;j<N;++j)
23             if(i&(1<<j)) cover[i]|=P[j];
24        }
25        for(i=1;i<(1<<N);++i)
26        {
27            for(int S=i;S;S=(S-1)&i)
28             if(cover[S]==(1<<N)-1&&f[i]<f[i^S]+1)
29             f[i]=f[i^S]+1;
30        }
31        printf("Case %d: %d
",++k,f[(1<<N)-1]);
32     }
33     return 0;
34 }