HDU 6006 Engineer Assignment （状态压缩DP）

/*
  一共有N个工作，M个人。每个工作需要某些领域的知识，每个人都有自己精通的领域。给这些工作分配人，要求每个人最多只能分配一项工作，每个工作的若干人所精通的知识必须包含了该工作的知识，
  问最多能分配几个工作。
  
  将人的集合表示成二进制
  dp[i][S]表示前i个工作，选的人的集合为S时，所完成任务的最大数量
  则有dp[i][S] = max( dp[i-1][S], dp[i-1][S ^ s] + 1 ), 其中s为S的子集，并且s所表示的人能够完成第i份工作
  
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 10;
vector<int> Work[maxn]; //每个工作所需的领域
vector<int> Peo[maxn];   //每个人精通的领域
vector<int> sets[maxn];  //sets[i]存储第i个工作可以由哪些人的集合来完成
bool Sets[maxn][1<<10]; //Sets[i][S]表示第i个工作是否可以由S集合来完成 （S为人的集合）
bool vis[105]; //领域，最多100个领域
int N, M;
int dp[maxn][1<<10];

void Input()
{
	for(int i = 0; i < 10; i++) { Work[i].clear(); Peo[i].clear(); sets[i].clear();}
	memset(Sets, false, sizeof Sets);
	int x, y;
    for(int i = 0; i < N; i++)
    {
    	scanf("%d", &x);
    	while(x--)
    	{
    		scanf("%d", &y);
    		Work[i].push_back(y);
    	}
    }

    for(int i = 0; i < M; i++)
    {
    	scanf("%d", &x);
    	while(x--)
    	{
    		scanf("%d", &y);
    		Peo[i].push_back(y);
    	}
    }
}

void Init()
{
	for(int S = 1; S < (1<<M); S++)
	{
		memset(vis, false, sizeof vis);
		for(int i = 0; i < M; i++) if(S & (1<<i))
		{
            for(int j = 0; j < Peo[i].size(); j++)
            	vis[Peo[i][j]] = true;
		}
		for(int i = 0; i < N; i++)
		{
			bool flag = true;
			for(int j = 0; j < Work[i].size(); j++) if(!vis[Work[i][j]])
			{
				flag = false;
				break;
			}
			if(flag) Sets[i][S] = true, sets[i].push_back(S);
		}
	}
}

void Solve(int &kase)
{
	int ans = 0;
	for(int i = 0; i < N; i++)
	  for(int S = 0; S < (1<<M); S++)
	  {
	  	  if(i == 0) { dp[i][S] = Sets[i][S]; ans = max(ans, dp[i][S]); continue; }
	  	  dp[i][S] = dp[i-1][S];
	  	  if(!Sets[i][S]) {ans = max(ans, dp[i][S]); continue;}
          for(int j = 0; j < sets[i].size(); j++)
          {
          	  int s = sets[i][j];
          	  if((S | s) == S)
          	    dp[i][S] = max(dp[i][S], dp[i-1][S ^ s] + 1);
          }
          ans = max(ans, dp[i][S]);
	  }
	  printf("Case #%d: %d\n", ++kase, ans);
}

int main()
{
	int T, kase = 0;
	scanf("%d", &T);
	while(T--)
	{
        scanf("%d%d", &N, &M);
        Input();
        Init();
        Solve(kase);
	}
}