Problem###
Miracle Corporations has a number of system services running in a distributed computer system which
is a prime target for hackers. The system is basically a set of N computer nodes with each of them
running a set of N services. Note that, the set of services running on every node is same everywhere
in the network. A hacker can destroy a service by running a specialized exploit for that service in all
the nodes.
One day, a smart hacker collects necessary exploits for all these N services and launches an attack
on the system. He finds a security hole that gives him just enough time to run a single exploit in each
computer. These exploits have the characteristic that, its successfully infects the computer where it
was originally run and all the neighbor computers of that node.
Given a network description, find the maximum number of services that the hacker can damage.
Input###
There will be multiple test cases in the input file. A test case begins with an integer N (1 ≤ N ≤ 16),
the number of nodes in the network. The nodes are denoted by 0 to N − 1. Each of the following
N lines describes the neighbors of a node. Line i (0 ≤ i < N) represents the description of node i.
The description for node i starts with an integer m (Number of neighbors for node i), followed by m
integers in the range of 0 to N − 1, each denoting a neighboring node of node i.
The end of input will be denoted by a case with N = 0. This case should not be processed.
Output###
For each test case, print a line in the format, ‘Case X: Y ’, where X is the case number & Y is the
maximum possible number of services that can be damaged.
Sample Input###
3
2 1 2
2 0 2
2 0 1
4
1 1
1 0
1 3
1 2
0
Sample Output###
Case 1: 3
Case 2: 2
题意##
n台计算机各运行n项服务，黑客进来后对每台电脑进行hack，对每台电脑可将它及与它相邻的电脑的某一服务搞垮。
问，在对n台电脑各自hack之后，最多有多少服务被完全搞垮（指没有一台电脑执行该服务）
题解##
看起来就像一道dp题，n还那么小，那就状压dp呗
问题是怎样设状态及转移
设p[i]表示第i台电脑及与它相邻的电脑组成的集合
题目相当于将p[1…n]分为若干组，每组包含所有电脑。要使组数最大
把p[i]进行二进制压位
设S为p[]的集合，dp[S]表示S集合最多分成满足要求的多少组
dp[S]=max { dp[S-S0]+1 | S0为S的子集，且S0为满足要求的一组 }
将S、S0也进行二进制压位，转移时枚举S0并判断即可
代码##
注：由于时间卡的比较紧，dp要写成递推形式的，递归形式会超时
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 18;
int n;
int p[N],dp[1<<N],cover[1<<N];
int main()
{
int m,x,kase=0;
while(scanf("%d",&n) && n){
for(int i=0;i<n;i++){
scanf("%d",&m);
p[i]=(1<<i);
for(int j=0;j<m;j++)
scanf("%d",&x),p[i]|=(1<<x);
}
for(int i=0;i<(1<<n);i++){
cover[i]=0;
for(int j=0;j<n;j++)
if(i&(1<<j)) cover[i]|=p[j];
}
int All=(1<<n)-1;
dp[0]=0;
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
",++kase,dp[All]);
}
return 0;
}