2014
03-03

# Uva-11825-Hacker’s Crackdown[状态DP]Java

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.

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.

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.

3
2 1 2
2 0 2
2 0 1
4
1 1
1 0
1 3
1 2
0

Case 1: 3
Case 2: 2

f(s)=max{(f(s0)|s0是s的子集,cover[s0]等于全集}+1;

Java代码：

import java.io.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main{
static int m,n;
static int maxn = 1<<17 ;
static int p[] = new int[20];
static int cover[] = new int[maxn];
static int ans[] = new int[maxn];
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("src/dp/in11825.txt"));
Scanner scan = new Scanner(new BufferedInputStream(System.in) );
int c = 0;
while(true){
n = scan.nextInt();
c++;
if(n == 0) break;
for(int i=0; i<n; i++){
m = scan.nextInt();
p[i] = 1 << i;
for(int j=0; j<m; j++){
int tmp = scan.nextInt();
p[i] |= ( 1<<tmp );//二进制上有1表示相连
}
//System.out.println(p[i]);
}

//做预处理。cover数组主要是用来判断哪些组合可以 完全的杀掉整个服务
for(int i=0; i< (1<<n); i++){
cover[i] = 0;
for(int j=0; j<n; j++){
if( (i & (1<<j)) != 0)
cover[i] |= p[j];
}
}
int all = (1<<n) - 1;
ans[0] = 0;
for(int s = 1; s < (1<<n); s++){
ans[s] = 0;
//枚举子集合。例如 二进制 111 的子集合为 (111,110,101,100,11,10,1)
for(int s0 = s; s0!=0; s0 = (s0-1)&s ){
//如果当前子集合s0，可以 杀掉整个服务。更新s
if( cover[s0] == all ){
ans[s] = Math.max( ans[s], ans[s ^ s0] +1);//
}
}
}
System.out.println("Case "+ c +": " + ans[all]);
}
}
}

1. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧