Uva(11825)(hackerscrackdown)

链接：https://vjudge.net/problem/UVA-11825
思路：首先要把题意抽象出来，可以理解为题目给你n个集合，让你尽可能合并成多个集合，使得每个集合都是电脑的全集，最后集合数就是答案，那么我们可以考虑把题目给的每个集合都表示成一个二进制的数，然后求出这些集合的所有子集，f(s) = max(f(s0)+1(其中s0是s的子集且s和s0的差集是一个全集)，接下来就可以用动态规划解决问题
附录：求所有i的子集：for(int j=i;j;j=(j-1)&i)

代码：

#include<iostream>
#include<cstring>
using namespace std;

int n,m,t;
int a[20];
int s[65660],f[65660],o=0;

int main(){
    while(cin>>n&&n){
        memset(a,0,sizeof(a));
        memset(s,0,sizeof(s));
        memset(f,0,sizeof(f));
        for(int i=0;i<n;i++){
            cin>>m;
            a[i]+=(1<<i);
            for(int j=0;j<m;j++){
                cin>>t;
                a[i]|=(1<<t);//将相邻电脑表示为一个二进制数
            }
        }
        for(int i=1;i<(1<<n);i++){
            for(int j=0;j<n;j++){
                if(i&(1<<j))
                    s[i]|=a[j];//求出这些相邻电脑组成集合（将其看为一个大集合的元素）的子集
            }
        }
        f[0] = 0;
        int all = (1<<n)-1;//全集
        for(int i=1;i<=(1<<n)-1;i++){
        for(int j=i;j;j=(j-1)&i){//j=(j-1)&i是一种遍历子集的写法，可以表示出所有子集，相当于每次去掉一个不同位置的1
        if(s[j]==all)
            f[i] = max(f[i],f[i^j]+1);//因为j是i的子集，所以i^j就是去除i中且j中共同1的位置，求得的就是i和j的差集，实在是很妙，一定要多多理解一下
            }
        }
    cout<<"Case "<<++o<<": "<<f[all]<<endl;
    }
    return 0;
}