题目大意就是有一个图，破坏一个点同时可以破坏掉相邻点。每个点可以破坏一次，问可以完整破坏几次，点数=16。
看到16就想到状压什么的。
尝试设状态：用f[i]表示选的情况是i(一个二进制串)，至少可以破坏几次。
那么就有这样的转移方式：
1.选走所有人用来破坏一次。
2.选举i的一个子集sub，f[i]=f[sub]+f[i-sub]。
然后发现这题就做完了。
具体做法：把每个人的破坏情况预处理一下，然后枚举全集i。
先全部选，看是否能破坏一层。
然后枚举子集，取max。
枚举子集方式:for(int sub=i;sub;sub=(sub-1)&i)。
一道颇有纪念意义的状压子集DP，复杂度O(3^n)。
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <cstring> #include <queue> #include <complex> #include <stack> #define LL long long int #define dob double #define FILE "11825" using namespace std; const int N = 100010; int bin[20],n,can[N],ban[20],t; inline int gi(){ int x=0,res=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();} while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*res; } int main() { freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); bin[0]=1;for(int i=1;i<=16;++i)bin[i]=bin[i-1]*2; while(n=gi()){ memset(can,0,sizeof(can)); for(int i=0;i<n;++i)ban[i]=bin[i]; for(int i=0;i<n;++i) for(int j=gi();j>=1;--j) ban[i]|=bin[gi()]; for(int opt=1;opt<bin[n];++opt){ for(int i=0;i<n;++i)if(opt&bin[i])can[opt]|=ban[i];can[opt]/=(bin[n]-1); for(int sub=(opt-1)&opt;sub;sub=(sub-1)&opt) can[opt]=max(can[opt],can[sub]+can[opt^sub]); } printf("Case %d: %d\n",t,can[bin[n]-1]); } fclose(stdin);fclose(stdout); return 0; }