题目链接：uva 11825
题意：
你是一个黑客，侵入了n台计算机（每台计算机有同样的n种服务），对每台计算机，你能够选择终止一项服务，则他与其相邻的这项服务都终止。你的目标是让很多其它的服务瘫痪（没有计算机有该项服务）。
思路：（见大白70页，我的方程与大白不同）
把n个集合P1、P2、Pn分成尽量多的组，使得每组中全部集合的并集等于全集，这里的集合Pi是计算机i及其相邻计算机的集合，用cover[i]表示若干Pi的集合S中全部集合的并集，dp[s]表示子集s最多能够分成多少组，则
假设cover[s]=all，那么dp[s]至少为1.
dp[s]=max(dp[s],dp[s0]+dp[s^s0]); （两个子集的和）
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 16
using namespace std; int n, m, x, dp[1<<N], cover[1<<N], p[N]; int main ()
{
int k = 0;
while(scanf("%d",&n), n)
{
for(int i = 0; i < n; i++)
{
p[i] = 1<<i;
scanf("%d",&m);
for(int j = 0; j < m; j++)
{
scanf("%d",&x);
p[i] |= 1<<x;
}
}
for(int s = 0; s < (1<<n); s++)
{
cover[s] = 0;
for(int i = 0; i < n; i++) if(s&1<<i)
cover[s] |= p[i];
}
dp[0] = 0;
int all = (1<<n)-1;
for(int s = 1; s < (1<<n); s++)
{
if(cover[s]!=all) dp[s] = 0;
else dp[s]=1;
for(int s0 = s; s0; s0 = (s0-1)&s) // 枚举子集的技巧 s0为s除空集之外的全部子集
{
dp[s] = max(dp[s], dp[s^s0]+dp[s0]);
}
}
printf("Case %d: %d\n",++k, dp[all]);
}
return 0;
}
/*
3
2 1 2
2 0 2
2 0 1 5
2 0 1
2 0 2
2 0 1
1 4
1 3 4
2 1 2
3 0 2 3
3 0 1 3
2 1 2
*/