UVa 11825 - Hackers' Crackdown

题目地址

描述

一个黑客入侵一个有 $n$ 台计算机 $(1, 2, \cdots n - 1)$ 的网络,一共有 $n(1 \leq n \leq 16)$ 种任务,每台计算机都运行这所有的任务。对于每台计算机可以选择一项服务,终止这台计算机与其相邻计算机之间的这种服务,你需要让尽量多的服务瘫痪。

分析

我们尝试把题意抽象一下,一共有 $n$ 个集合 $sub_{1}, sub_{2}, \cdots, sub_{n}$,将这些集合分成尽量分成多组,使得每组的集

合的并集等于全集。

因为 $n$ 很小,所以考虑状态压缩,我们用二进制来表示这些集合。

如果第 $i$ 台电脑与第 $j$ 台电脑相连,那么集合 $sub[i]$ 的第 $j$ 位为 $1$。

1
2
3
4
5
6
7
8
for (register int i = 0; i < n; ++i) {
int num = readIn();
sub[i] = 1 << i;
for (register int j = 1; j <= num; ++j) {
int cur = readIn();
sub[i] |= (1 << cur);
}
}

接下来预处理 $2^{n}$ 种集合组合的并集

1
2
3
4
5
6
for (register int S = 0; S < (1 << n); ++S) {
cover[S] = 0;
for (register int i = 0; i < n; ++i) if (S & (1 << i)) {
cover[S] |= sub[i];
}
}

令 $f[S]$ 为子集 $S$ 最多可以分为多少可以覆盖全集的组合,有转移

枚举集合的子集的小技巧 :

1
2
3
4
5
6
7
8
f[0] = 0;
int sum = (1 << n) - 1;
for (register int S = 1; S < (1 << n); ++S) {//
f[S] = 0;
for (register int S0 = S; S0; S0 = (S0 - 1) & S) {
if (cover[S0] == sum) f[S] = max(f[S], f[S ^ S0] + 1);
}
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//  Created by ZJYelizaveta on 2017年08月27日 星期日 20时34分04秒
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
inline int readIn() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 16 + 3;
const int MAXNODE = 1 << MAX_N;
const int INF = 0x3f3f3f3f;
int testCase;
int n;
int sub[MAXNODE], f[MAXNODE], cover[MAXNODE];

inline void solve() {
for (register int S = 0; S < (1 << n); ++S) {
cover[S] = 0;
for (register int i = 0; i < n; ++i) if (S & (1 << i)) {
cover[S] |= sub[i];
}
}

f[0] = 0;
int sum = (1 << n) - 1;
for (register int S = 1; S < (1 << n); ++S) {//
f[S] = 0;
for (register int S0 = S; S0; S0 = (S0 - 1) & S) {
if (cover[S0] == sum) f[S] = max(f[S], f[S ^ S0] + 1);
}
}
}

int main()
{
testCase = 0;
while (scanf("%d", &n) && n != 0) {
for (register int i = 0; i < n; ++i) {
int num = readIn();
sub[i] = 1 << i;
for (register int j = 1; j <= num; ++j) {
int cur = readIn();
sub[i] |= (1 << cur);
}
}
// for (int i = 0; i < n; ++i) printf("%d\n", sub[i]);
solve();
printf("Case %d: %d\n", ++testCase, f[(1 << n) - 1]);
}
return 0;
}
Partager