UVA 11825: Hacker’s Crackdown —— 状压 DP

题目链接

题目大意:

给你一台有 $n$ 台计算机的计算机系统网络,每台电脑上都运行着相同的 $n$ 个服务。一个黑客每次可以停止这个计算机网络中一台电脑的一种服务。当一台计算机的一种服务被停止时,它相邻的计算机的该服务也会停止。当所有的电脑都停止运行某种服务时,该服务被认为是已经被摧毁了。最多可以摧毁多少种服务。

输入格式:

多组数据。

对于每组数据,第一行一个整数 $n$ ( $1 \leq n \leq 16$ ),代表系统网络中计算机的数量, $n = 0$ 时输入结束。接下来 $n$ 行,每行第一个整数 $m$ 代表与第 $i$ 台计算机相邻的计算机数量。接下来 $m$ 个数代表与第 $i$ 台计算机相邻的计算机的编号。

输出格式:

对于每组测试数据,输出最多能摧毁的服务数量。格式与样例一致。

测试样例:

Input
3
2 1 2
2 0 2
2 0 1
4
1 1
1 0
1 3
1 2
0
Output
Case 1: 3
Case 2: 2

分析:

首先看一下数据范围: $1\leq n \leq 16$ ,非常小,所以自然而然想到状态压缩

所以我们把每台计算机相邻的节点编号保存成一个状态存在 $link[]$ 数组里面, $link_i$ 保存的是与第 $i$ 台计算机相邻的节点 (包括它自己) 。

接下来我们枚举所有的电脑集合,记录每个集合的电脑可以连到的所有电脑的集合。保存在 $cover[]$ 数组里。 $cover_S$ 代表电脑集合 $S$ 可以覆盖的集合。具体操作如下:

for (int S = 0; S < (1 << n); ++S) {
  cover[S] = 0;
  for (int i = 0; i < n; ++i) {
    if ((S & (1 << i))) cover[S] |= link[i];
  }
}

最后进行动态规划。对于一个集合 $S$, 我们枚举枚举它的所有的子集,若它的子集 $S0$ 可以覆盖全集,则答案就要加上 $S$ 集合中减掉 $S0$ 集合的元素后得到的集合的方案数。

if (cover[S0] == ALL) dp[S] = max(dp[S], dp[S ^ S0] + 1);

最后,设全集为 $ALL$ , $dp_{ALL}$ 就是答案。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;

template<class _T> inline void read(_T &_x) {
  int _t, _flag = 0;
  while ((_t = getchar()) != '-' && (_t < '0' || _t > '9'));
  if (_t == '-')  _t = getchar(), _flag = 1;
  _x = _t - '0';
  while ((_t = getchar()) >= '0' && _t <= '9')
    _x = _x * 10 + _t - '0';
  if (_flag)  _x = -_x;
}

typedef long long ll;
typedef pair<int, int> pii;

const int MAX_S = 1 << 20, MAX_N = 20;
int link[MAX_N], cover[MAX_S], dp[MAX_S];
int n, ALL;

void init() {
  memset(link, 0, sizeof(link));
  memset(cover, 0, sizeof(cover));
  memset(dp, 0, sizeof(dp));
}

void get_cover() {
  for (int S = 0; S < (1 << n); ++S) {
    cover[S] = 0;
    for (int i = 0; i < n; ++i) {
      if ((S & (1 << i))) cover[S] |= link[i];
    }
  }
}

void DP() {
  dp[0] = 0;
  for (int S = 1; S < (1 << n); ++S) {
    dp[S] = 0;
    for (int S0 = S; S0; S0 = (S0 - 1) & S) {
      if (cover[S0] == ALL) dp[S] = max(dp[S], dp[S ^ S0] + 1);
    }
  }
}

int main() {
  read(n);
  int kase = 0;
  while (n) {
    init();
    ALL = (1 << n) - 1;
    for (int i = 0; i < n; ++i) {
      link[i] = (1 << i);
      int num;
      read(num);
      while (num--) {
        int neb;
        read(neb);
        link[i] |= (1 << neb);
      }
    }
    get_cover();
    DP();
    printf("Case %d: %d\n", ++kase, dp[ALL]);
    read(n);
  }
}