Uva11825-Hackers’Crackdown状态压缩DP

题意:

有N个电脑..每个电脑都运行着N个相同的进程..现在来黑这些电脑..对于每个电脑..可以黑掉它的一个进程..这么做..和它相邻电脑的这个进程也会崩溃..如果一个进程 没有一台电脑运行了..就那么这个进程就挂了..问最多能挂掉多少个进程.

题解:

也不算题解了..自己没想出来..参考了别人的思想....只是说下自己的理解..

将每个点i以及其相邻的点看成集合..一共N个集合...这N个集合..对于每一个集合..只要黑i的某个进程..相邻的这个进程自然崩溃..也就是说.对于每个集合..必定可以在这个集合内把一个进程崩溃..而对于整个系统..一个进程要挂掉...就必定需要若干个集合的并..点数=N...问题转换..求最多的不相交的集合并..使得每一个集合并点数=N..并且集合并的个数最多...

首先把每个电脑相邻(包括)自己的情况用二进制表示出来..再将所有电脑组合的情况包括的电脑情况用二进制表示出来...这里很直接..主要是dp的状态转移..

dp[i] = max ( dp [i^k]+1 )

其中i表示的集合并必须覆盖到所有N个点..k是i的子集..i^k就是i对于k的补集..保证两个集合不相交..因为对于i来说只能多让一个进程挂..所以+1

Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<algorithm>
#define ll long long
#define oo 1000000007
#define pi acos(-1.0)
#define MAXN 17
using namespace std;   
int n,A[MAXN],S[1<<MAXN],C[1<<MAXN],dp[1<<MAXN]; 
int main()
{      
       int i,x,cases,totol; 
       cases=0;
       while (~scanf("%d",&n) && n)
       {
               for (i=0;i<n;i++)
               {
                     int m;
                     scanf("%d",&m);
                     A[i]=(1<<i);
                     while (m--)
                     {
                           int x;
                           scanf("%d",&x);
                           A[i]|=(1<<x);
                     }
               }
               totol=(1<<n)-1;
               for (i=0;i<=totol;i++)
               {
                     C[i]=0;
                     for (x=0;x<n;x++)
                        if (i&(1<<x)) C[i]|=A[x];
               }
               for (i=0;i<=totol;i++)
               {
                     dp[i]=0;
                     if (C[i]!=totol) continue;
                     for (int k=i;k;k=(k-1)&i)
                        if (C[k]==totol) 
                           dp[i]=max(dp[i],dp[k^i]+1);
               }
               printf("Case %d: %d\n",++cases,dp[totol]);      
       } 
       return 0;
}