UVA 11825 Hackers’ Crackdown 状压DP枚举子集势
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 = , M = , mod = 1e9+, inf = 0x3f3f3f3f;
typedef long long ll;
//不同为1,相同为0 int dp[<<N],c[<<N],x,n,cas = , point[<<N];
int main() {
while(scanf("%d",&n) == && n) {
for(int i=;i<n;i++) {
scanf("%d",&x);int j;
point[i] = (<<i);
while(x--) scanf("%d",&j), point[i]|=(<<j);
}
for(int i=;i<(<<n);i++) {
c[i] = ;
for(int j=;j<n;j++) {
if(i&(<<j)) c[i]|=point[j];
}
}
for(int i=;i<(<<n);i++) {
dp[i] = ;
for(int j=i;j;j = (j-)&i) {
if(c[j] == (<<n) - ) dp[i] = max(dp[i], dp[i^j] + );
}
}
printf("Case %d: %d\n", ++cas, dp[(<<n) - ]);
}
}
最新文章
- 转:delphi 删除指定文件夹下所有文件
- PHP文件读写操作之文件写入代码
- 济南学习D2T2__数学分析题
- 第六篇 :微信公众平台开发实战Java版之如何自定义微信公众号菜单
- MySQL基础之第1章 数据库概述
- struts2.1笔记03:AOP编程和拦截器概念的简介
- JAVA学习:方法
- UWP 页面间传递参数(常见类型string、int以及自定义类型)
- Java 反射(二)
- 学习TensorFlow,生成tensorflow输入输出的图像格式
- 学习ASP.NET Core Razor 编程系列十九——分页
- React-typescript-antd 常见问题
- iproute
- Texture转Texture2D
- script weixin app / weixin xiao chen xu
- [Java代码] Java用pinyin4j根据汉语获取各种格式和需求的拼音
- 201621123001 《Java程序设计》第10周学习总结
- Flutter学习之制作底部菜单导航
- 201621123010《Java程序设计》第4周学习总结
- Template7学习记录