uva11825(状态压缩+枚举子集)黑客的攻击

2017年07月15日 8点热度 0人点赞 0条评论

例题29 黑客的攻击(Hacker's Crackdown, UVa 11825
假设你是一个黑客, 侵入了一个有着
n台计算机(编号为01n
1) 的网络。 一共有n种服务, 每台计算机都运行着所有服务。 对于每
台计算机, 你都可以选择一项服务, 终止这台计算机和所有与它相邻计
算机的该项服务(如果其中一些服务已经停止, 则这些服务继续处于停
止状态) 。 你的目标是让尽量多的服务器完全瘫痪(即: 没有任何计算
机运行该项服务) 。
【输入格式】
输入包含多组数据。 每组数据的第一行为整数
n1≤n≤16) ; 以下n
行每行描述一台计算机的相邻计算机, 其中第一个数m为相邻计算机个
数, 接下来的
m个整数为这些计算机的编号。 输入结束标志为n0
【输出格式】
对于每组数据, 输出完全瘫痪的服务的最大数量。
【分析】
本题的数学模型是: 把
n个集合P
1P2Pn分成尽量多组,
使得每
组中所有集合的并集等于全集。 这里的集合
P

i就是计算机i及其相邻计算机的集合, 每组对应于题目中的一项服务。 注意到n很小,
可以用《算法

竞赛入门经典》 中提到的二进制法表示这些集合, 即在代码中, 每个集
Pi实际上是一个非负整数。 

/*
本文的题意要注意的地方是如果一个电脑被入侵了,
那么它的相邻的电脑的相邻的电脑也会是被入侵了
p[i]表示的与i直接相邻的一个状态,没太大直接意义,主要是为了推出cover的状态
cover[s]表示的是s状态被选择时,n个电脑被覆盖的状态
f[s]表示s状态被选择,已经被入侵的最大服务数
用到枚举子集,假设集合s为i的一个子集,则(s-1)&i为i的下一个子集,直至s为0.
其实就是一个状态能够达到全集,然后和另外一个状态合并成一个新的状态,然后就是dp取最大值
*/
#include
#include
using namespace std;
const int mn=20,ms=(1<<16)+5;
int p[20],f[ms],cover[ms];
int main()
{
    int n,kcase=1;
    while(~scanf("%d",&n)&&n)
    {
        for(int i=0; i

未经允许不得转载!uva11825(状态压缩+枚举子集)黑客的攻击

update

纸上得来终觉浅, 绝知此事须躬行。