UVa 11825




【Topic Link】

Hackers’ Crackdown

【题意】

有N台机器,每台机器上有N个服务

你可以对每台机器选择关闭他以及和他相邻的机器的一种服务

当所有机器不能运行一个服务时,就是摧毁了一种服务

问你最多能摧毁多少个服务

【题解】

就是把n台电脑看成n个集合,每个集合的成员就是这台电脑,以及和这台电脑相邻的电脑;
我们就是要求把这些集合合并成尽量多的大集合,使每个集合都等于全集;也就是因为最开始的小集合,我们可以让它里面全部电脑的某一项服务全部失误,那如果合并成一个大集合,则这个大集合的某一项服务可以全部失效;所以能合并成几个等于全集的大集合,就可以让几项服务失效;

【Tip】

状态压缩,异或操作是相同得0,不同得1.LRJ这道题的位运算用的好…

【Source Code】

github: Uva 11825.cpp


#include<bits/stdc++.h>
using namespace std;
int N,T,P[1<<17],f[1<<17],cover[1<<17],ca=1;
int main(){
    while(~scanf("%d",&N),N){
        ///初始化第i台计算机的相邻集合
        for(int i=0;i<N;++i){
            int n,m;
            scanf("%d",&n);
            P[i]=1<<i;
            for(int j=0;j<n;++j){
                scanf("%d",&m);
                P[i] |= 1<<m;
            }
        }
        ///S是N个计算机的所有组合的集合,二进制表示,cover[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] |= P[i];///第i台机器选/不选
            }
        }
        f[0]=0;
        int ALL=(1<<N)-1;///全集二进制表示
        for(int S=1;S<(1<<N);++S){
            f[S]=0;
            ///筛出S的子集进行动态规划
            for(int S0=S;S0;S0=(S0-1)&S){
                if(cover[S0]==ALL)///如果子集S的子集的并是全集
                    f[S]=max(f[S],f[S^S0]+1);
            }
        }
        printf("Case %d: %d\n",ca++,f[ALL]);
    }
    return 0;
}