博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
UVA 11825 Hackers’ Crackdown(集合动态规划 子集枚举)
阅读量:6689 次
发布时间:2019-06-25

本文共 2570 字,大约阅读时间需要 8 分钟。

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 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 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 lines describes the neighbors of a node. Line i (0<=i<N) represents the description of node i. The description for node starts with an integer (Number of neighbors for node i), followed by integers in the range of 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种服务,每台计算机都运行着所有的服务。对于每台计算机,你都可以选择一项服务,终止这台计算机和所有与它相邻计算机的该项服务(如果其中一些服务已经停止,则这些服务继续处于停止状态)。你的目标是让尽量多的服务器完全瘫痪(即:没有任何计算机运行该项服务)

输入格式:输入包含多组数据。每组数据的第一行为整数n(1<=n<=16);以下n行每行描述一台计算机的相邻计算机,其中第一个数m为相邻计算机个数,接下来的m个整数位这些计算机的编号。输入结束标志为n=0。

输出格式:对于每组数据,输出完全瘫痪的服务器的最大数量。

分析:

  本题的数学模型是:把n个集合p1,p2,…pn分成尽量多组,使得每组中所有集合的并集等于全集。这里的集合P就是计算机 i 及其相邻计算机的集合,每组对应于题目中的一项服务。注意到n很小,可以用二进制法表示这些集合,即在代码中,每个集合P实际上是一个非负整数。输入的部分代码如下:

for(int i=0;i

  为了方便,我们用cover(S)表示若干P的集合S中所有Pi 的并集(二级制表示),即这些Pi 在数值上“按位或”。

for(int S = 0; S < (1<

想到这样的动态规划:用f(S)表示子集S最多可以分成多少组,则

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

这里有一个重要的技巧:枚举S的子集S0。详见下面代码。

int ALL = (1<

 

完整代码如下:

1 #include
2 #include
3 using namespace std; 4 5 const int maxn = 16; 6 int n, P[maxn], cover[1<

 

注意:位运算符的优先级比较低,注意加括号

转载地址:http://kezoo.baihongyu.com/

你可能感兴趣的文章
我的友情链接
查看>>
编辑vi 查看网卡命令
查看>>
常见的内存错误及其对策
查看>>
C语言:冒泡法排序一组数,如何优化?
查看>>
分享16个javascript&jQuery的MVC教程
查看>>
使用MediaElement.js构建个性的HTML5音频和视频播放器
查看>>
阿里云域名配置与解析
查看>>
常用的.net开源项目
查看>>
until 循环:实现一个shell脚本,不停地询问用户要执行什么操作,直到用户输入quit才会退出...
查看>>
thinkphp中无法加载数据库驱动
查看>>
MyBatis的xml文件增量热加载,支持多数据源
查看>>
wine安装的软件如何卸载
查看>>
C语言中基本的数据类型 和常用表达式
查看>>
More Fileds的直接输出和获取自定义字段的方法
查看>>
12.1LNMP架构介绍12.2MySQL安装12.312.4 PHP安装12.5Nginx安装
查看>>
ubuntu下安装ROR
查看>>
工作流调度
查看>>
Nginx TCP代理和负载均衡
查看>>
理解原型对象
查看>>
Apache虚拟目录
查看>>