题目链接Click Here
【题目描述】
假如你是一个黑客，侵入了一个有着\(n\)台计算机（编号为\(1.2.3....n\)）的网络。一共有\(n\)种服务，每台计算机都运行着所有服务。对于每台计算机，你都可以选择一项服务，终止这台计算机和所有与它相邻计算机的该项服务（如果其中一些服务已经停止，那他们继续保持停止状态）。你的目标是让尽量多的服务完全瘫痪(即：没有任何计算及运行着该服务)
【输入格式】
输入包含多组数据，每组数据的第一行为整数\(n(1<=n<=16)\):以下\(n\)行每行描述一台计算机相邻的计算机，其中第一个数\(m\)为相邻计算机个数，接下来的\(m\)个整数为这些计算机的编号。输入结束标志\(n=0\)。
【输出格式】
对于每组数据，输出完全瘫痪的服务的数量。
本题实际上可以转化为：给你\(n\)个集合\(p_{1 -> n}\)，你要把它们分成尽可能多的组，每个组内所有集合的并等于全集。
因为\(n\)比较小，所以我们可以把每个集合\(P\)（每个点自身\(+\)它相邻的点）二进制状压。考虑选取一些集合时，把选取的集合也二进制状压（表示为\(S\)），存一下该选取状态下可以覆盖的状况即可（\(cover_s\)）。
这样我们可以得到方程：
\[f(S) = max (f(S - S_0)|S_0∈S, cover_{S_0} = S_{All})\]
技巧：二进制下的子集枚举：
for (int S0 = S; S0 != 0; S0 = (S0 - 1) & S) 这样为什么能实现子集枚举呢？请读者自行思考（笑
复杂度：\(O(\sum_{k=1->N}C(n, k) * 2 ^ n) = O(3 ^ n)\)。为什么等于后面我不会二项式定理所以不大会。
关注点：本题中的子集枚举思想。
#include <bits/stdc++.h>
using namespace std;const int N = 20;int Case, n, m, to, s[N], f[N], cho[1 << N];int main () {
// freopen ("data.in", "r", stdin);while (cin >> n && n) {for (int i = 0; i < n; ++i) {cin >> m; s[i] = 1 << i;for (int j = 0; j < m; ++j) {cin >> to; s[i] |= 1 << to;}
// cout << "s[" << i << "] = " << s[i] << endl;} const int All = (1 << n) - 1;for (int i = 0; i < 1 << n; ++i) {cho[i] = 0;for (int k = 0; k < n; ++k) {if ((i >> k) & 1) {cho[i] |= s[k];}}}f[0] = 0;for (int S = 1; S < (1 << n); ++S) {f[S] = 0;for (int S0 = S; S0; S0 = (S0 - 1) & S) { //枚举S的子集 if (cho[S0] == All) {f[S] = max (f[S], f[S ^ S0] + 1);}}}cout << "Case " << ++Case << ": " << f[All] << endl;}
}