首页 > ACM题库 > UVA > Uva-11825-Hacker’s Crackdown[状态DP]Java
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

转化为数学模型:有n个节点,每个节点有m_i个邻居,每个人和邻居为一个整体,问最多可以分成几组使得每组并集合为全集。

书上给的策略也就是

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

这个题因为n范围的原因使得我们可以用二进制进行表示,首先找到每台机子能够连接的所有机子,然后cover(s)表示pi的集合s中所有pi的并集,其实就是说以当前点进行操作最多可以使得多少台机子停止工作。

然后后面只需要枚举s的子集s0即可,这里不得不佩服作者用的这个技巧,即s0=(s0-1)&s这样便使得s的子集全部找到,受教了!

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小值吧