代码就是书上的 这题太神了 太好了
直接看书吧孩子 书上讲的蛮好的
2进制枚举子集还是很巧妙的
a[i]表示的树中1的地方表示相连 所有1组成一个集合
cover[i]表示a[i]的组合 比如i = 6 就是 110 就是a[1] a[2]2个集合的并集
dp[i]表示集合i做多终止几项服务
for(int s0 = s; s0; s0 = (s0-1)&s)
s0 枚举了s的子集 可以自己比划一下
如果cover[s0] == all (all全为1) 那么是s^s0 的部分也有可能终止服务
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[1<<20];
int cover[1<<20];
int a[1<<20];
int main()
{
int cas = 1;
int n, i, j;
while(scanf("%d", &n) && n)
{
int m, x;
for(i = 0; i < n; i++)
{
scanf("%d", &m);
a[i] = 1 << i;
while(m--)
{
scanf("%d", &x);
a[i] |= (1<<x);
}
}
for(int s = 0; s < (1<<n); s++)
{
cover[s] = 0;
for(i = 0; i < n; i++)
{
if(s & (1<<i))
cover[s] |= a[i];
}
}
dp[0] = 0;
int all = (1<<n) - 1;
for(int s = 1; s < (1<<n); s++)
{
dp[s] = 0;
for(int s0 = s; s0; s0 = (s0-1)&s)
{
if(cover[s0] == all)
dp[s] = max(dp[s], dp[s^s0]+1);
}
}
printf("Case %d: %d\n", cas++, dp[all]);
}
return 0;
}