Hackers' Crackdown UVA - 11825
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
题解:
这个题目首先把模型抽象出来,n个集合,将每个集合分组,使得每组集合元素的并的于全集,求最多可以分成多少组。
首先集合有关,我们数据范围16,我们首先想到子集dp,设dp[S],表示集合S中各个元素的并等于全集的数量,那么转移十分好转dp[S]=dp[S-S次]+1,S次 是S的子集,且S次的并等于全集。
但实现起来还是十分麻烦,首先我们可以用二斤制压缩来表示一个电脑集合p[i],p[now]|=1<<x;其次就是集合取并集,我们用“|”来实现,就是如果包括这个元素i那么就|=p[i],最后是枚举子集,枚举集合S的子集S0我们可以for(int s0=s;s0;s0=(s0-1)&s),这个还比较玄学吧。
代码:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#define MAXN 20
using namespace std;
int n,m;
int dp[<<MAXN],cover[<<MAXN],p[MAXN]; void cl(){
memset(p,,sizeof(p));
memset(dp,,sizeof(dp));
memset(cover,,sizeof(cover));
} int main(){
int ca=;
while(){
cl();
scanf("%d",&n);
if(!n) break;
for(int now=;now<n;now++){
scanf("%d",&m);
for(int i=;i<=m;i++){
int x;scanf("%d",&x);
p[now]|=<<x;
}
p[now]|=<<now;
}
int all=(<<n)-;
for(int s=;s<=all;s++){
for(int i=;i<n;i++)
if(s&(<<i)) cover[s]|=p[i];
}
for(int s=;s<=all;s++){
for(int s0=s;s0;s0=(s0-)&s){
if(cover[s0]==all) dp[s]=max(dp[s],dp[s^s0]+);
}
}
printf("Case %d: %d\n",++ca,dp[all]);
}
}
最新文章
- Java(JCo3)与SAP系统相互调用
- load mainaccount
- axis
- 32、shiro 框架入门三
- Oracle定义varchar2()类型存储汉字的长度问题
- 九幽史程博:助力国内开发者借Win10东风出海
- sql 语句大小写的问题
- Linux-CentOS6.4-PXE-DHCP-FTP
- 浅谈 OneAPM 在 express 项目中的实践
- C语言第六节基本运算符
- 转载 asp.net中ViewState的用法详解
- 从零开始 WIN8.1 下Android 开发环境搭建
- ActiveMQ的入门demo
- SAP CRM 为用户创建业务合作伙伴并分配到组织单位
- 关于Context []startup failed due to previous errors有效解决方式
- STM32CubeMX GPIO的使用
- [C#]使用dnSpy对目标程序(EXE或DLL)进行反编译修改并编译运行
- 冲刺总结随笔(Alpha)
- SpriteBuilder中粒子发射器的reset on visibility toggle选项解释
- List接口和Set接口和Map接口的of方法
热门文章
- 原创 | 手摸手带您学会 Elasticsearch 单机、集群、插件安装(图文教程)
- pycharm中报ImportError: libcublas.so.9.0错误的解决方法。
- Django中自定义模型管理器(Manager)及方法
- .Net WCF服务部署IIS详细解析
- UITableView tableHeaderView 自动布局
- net core WebApi——定时任务Quartz
- Django&;,Flask&;pyrthon原生sql语句 基本操作
- Nginx反向代理之动静分离
- Android Studio [相对布局RelativeLayout]
- JAVA Atm测试实验心得