假设你是一个黑客，入侵了一个有着n台计算机（编号为0,1,2,…n-1）的网络。一共有n种服务，每台计算机都运行着所有的服务。对于每台计算机，你都可以选择一项服务，终止这台计算机和所有与它相邻计算机的该项服务（如果其中一些服务已经停止，则这些服务继续处于停止状态）。你的目标是让尽可能多的服务瘫痪（即：没有任何计算机运行该项服务）。
输入描述:
多组数据，以n=0结尾。
每组数据第一行包含一个整数n，n<=16。
接下来，每行包括m+1个整数，其中第一个整数为m，表示受这台电脑服务的电脑台数；然后m个整数，表示这些电脑的编号。电脑的编号为0到n-1之间的整数。
输出描述:
对于每组数据，输出完全瘫痪的服务的最大数量。
示例1
输入
3
2 1 2
2 0 2
2 0 1
4
1 1
1 0
1 3
1 2
0
输出
3
2
说明
n<=16
diannaobingdu.cppview raw1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N = 20;
int n, m;
int edge[N];
int dp[1<<N], arrive[1<<N];
int main(){
while(scanf("%d", &n), n!=0){
memset(dp, 0, sizeof dp);
memset(arrive, 0, sizeof arrive);
memset(edge, 0, sizeof edge);
for(int i=0;i<n;i++){
scanf("%d", &m);
edge[i]|=(1<<i);
int x;
while(m--)
{
scanf("%d", &x);
edge[i]|= (1<<x);
}
}
for(int i=0;i<1<<n;i++){
for(int j=0;j<n;j++){
if(i>>j&1) arrive[i] |= edge[j];
}
}
for(int i=1;i<1<<n;i++){
int ans = 0;
for(int j=i;j;j=(j-1)&i){
if(arrive[j] == (1<<n)-1)
ans = max(ans, dp[i^j] + 1);
}
dp[i] = ans;
}
printf("%d\n", dp[(1<<n)-1]);
}
return 0;
}
|