Hackers’ Crackdown
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 Nservices. 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
Output for Sample Input
Case 1: 3
Case 2: 2
题意：
（黑客的攻击）假设你是一个黑客，侵入了了一个有着n台计算机（编号为0，1，…，n-1）的网络。一共有n种服务，每台计算机都运行着所有的服务。对于每台计算机，你都可以选择一项服务，终止这台计算机和所有与它相邻计算机的该项服务（如果其中一些服务已经停止，则这些服务继续处于停止状态）。你的目标是让尽量多的服务器完全瘫痪（即：没有任何计算机运行该项服务）
题解：
先把每个点集能覆盖到的电脑cover预处理出来。然后枚举每个状态，枚举每个状态的子集，如果该子集能覆盖到全部，状态转移就+1。
状态转移方程 dp[state] = dp[state - substate] + (substate == ((1<<n) - 1));
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int N = 17, M = 30005, mod = 1e9+7, inf = 0x3f3f3f3f; typedef long long ll; //不同为1，相同为0 int dp[1<<N],c[1<<N],x,n,cas = 0, point[1<<N]; int main() { while(scanf("%d",&n) == 1 && n) { for(int i=0;i<n;i++) { scanf("%d",&x);int j; point[i] = (1<<i); while(x--) scanf("%d",&j), point[i]|=(1<<j); } for(int i=0;i<(1<<n);i++) { c[i] = 0; for(int j=0;j<n;j++) { if(i&(1<<j)) c[i]|=point[j]; } } for(int i=1;i<(1<<n);i++) { dp[i] = 0; for(int j=i;j;j = (j-1)&i) { if(c[j] == (1<<n) - 1) dp[i] = max(dp[i], dp[i^j] + 1); } } printf("Case %d: %d ", ++cas, dp[(1<<n) - 1]); } }