HDU 6006 Engineer Assignment（状态压缩dp）

Engineer Assignment

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 508    Accepted Submission(s): 170

Problem Description

In Google, there are many experts of different areas. For example, MapReduce experts, Bigtable experts, SQL experts, etc. Directors need to properly assign experts to various projects in order to make the projects going smoothly.
There are N projects owned by a director. For the ith project, it needs Ci different areas of experts, ai,0,ai,1,⋅⋅⋅,ai,Ci−1 respective. There are M engineers reporting to the director. For the ith engineer, he is an expert of Di different areas, bi,0,bi,1,...,bi,Di−1.
Each engineer can only be assigned to one project and the director can assign several engineers to a project. A project can only be finished successfully if the engineers expert areas covers the project areas, which means, for each necessary area of the project, there is at least one engineer
masters it.
The director wants to know how many projects can be successfully finished.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line consisting of 2 integers, N the number of projects and M the number of engineers. Then N lines follow. The ith line containing the information of the ith project starts
with an integer Ci then Ci integers follow, ai,0,ai,1,...,ai,Ci−1 representing the expert areas needed for the ith project. Then another M lines follow. The ith line containing the information of the ith engineer starts with an integer Di then Di integers follow, bi,0,bi,1,...,bi,Di−1 representing the expert areas mastered by ith engineer.

Output

For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the maximum number of projects can be successfully finished.

limits
∙1≤T≤100.
∙1≤N,M≤10.
∙1≤Ci≤3.
∙1≤Di≤2.
∙1≤ai,j,bi,j≤100.

Sample Input

1 3 4 3 40 77 64 3 10 40 20 3 40 20 77 2 40 77 2 77 64 2 40 10 2 20 77

Sample Output

Case #1: 2

Hint

For the first test case, there are 3 projects and 4 engineers. One of the optimal solution is to assign the first(40 77) and second engineer(77 64) to project 1, which could cover the necessary areas 40, 77, 64. Assign the third(40 10) and forth(20 77) engineer to project 2, which could cover the necessary areas 10, 40, 20. There are other solutions, but none of them can finish all 3 projects. So the answer is 2.

Source

2016 CCPC-Final

        看到数据范围这么的小，想了想搜索还是差了一点，于是就只能是状压了……

        大致题意是，有n个项目，每个项目都涉及到一些领域，然后有m个专家，每个专家也都精通一些领域。规定每个专家只能参与一个项目，可以在一个项目中负责多个领域，然后每个项目一定得保证所有的领域至少都有一个人精通才能完成。问最后最多能够完成多少个项目。

        我们发现专家总共只有10个，然后项目也最多只有10个，所以我们可以定义dp[i][s]表示对于前i个项目，我选用专家的状态为s的时候最多能够完成的项目个数。这里s是一个10位的二进制数字，对应位置的0和1表示对应的专家是否已经被选用。然后看转移，当往后转移的时候，由于新增加了一个项目，所以改变量只是1，即要么这个新的项目被完成，要么未完成。而要完成这个项目，就得利用之前未被选用的专家。所以我们很自然的可以有转移方程dp[i][s]=dp[i-1][s]；和dp[i][s]=max(dp[i-1][s],dp[i-1][x]+1)；其中，这个状态x满足是状态s的子集，而且状态s-x可以满足完成项目i。这里的"-"表示查集的意思。

        接下来我们看复杂度，如果直接枚举s和x的话，再加上i，复杂度就是O(T*N*2^(2M))，对于N=M=10、T=100的数据来说是不能够接受的。所以我们考虑预处理出这个满足条件的x或者说满足条件的s-x，即至少s-x状态对应的专家要能够完成项目i。对于这个，其实也很好处理，我们事先对每个项目涉及到的领域和专家精通的领域进行离散化处理，然后对应也用状态压缩表示专家精通的领域和项目涉及到的领域。枚举所有的专家选取状态，求出对应能够覆盖的领域的状态，与每个项目的状态进行交集比较即可判定是否该状态的专家能够完成项目i。如此下来，复杂度大幅度优化，事实证明也是速度惊人。另外，在进行位运算的时候，要注意1<<x的时候，如果结果会超过int的范围，不仅结果要使用LL类型，而且这个”1“也要强制转换为”1LL“，因为这个浪费了好多时间……具体见代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int dp[11][1<<11];
LL project[11],engineer[11];
int number[11],tot,n,m,num;
vector<int> ST[11];
int mp[110];

void init()
{
    num=0;
    memset(ST,0,sizeof(ST));
    memset(mp,0,sizeof(mp));
    memset(project,0,sizeof(project));
    memset(engineer,0,sizeof(engineer));
}

int main()
{
    int T,tt=0;
    scanf("%d",&T);
    while (T--)
    {
        init();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            int c; scanf("%d",&c);
            for(int j=1;j<=c;j++)
            {
                int x; scanf("%d",&x);
                if (!mp[x]) mp[x]=++num;
                project[i]|=(1LL<<mp[x]);					//状态压缩处理每个项目涉及到的领域
            }
        }
        for(int i=1;i<=m;i++)
        {
            int c; scanf("%d",&c);
            for(int j=1;j<=c;j++)
            {
                int x; scanf("%d",&x);
                if (!mp[x]) mp[x]=++num;
                engineer[i]|=(1LL<<mp[x]);					//状态压缩处理每个专家精通的领域
            }
        }
        for(int i=0;i<(1<<m);i++)						//枚举专家选取的状态
        {
            tot=0; int x=i; LL status=0;
            while(x) {number[++tot]=x&1;x>>=1;}
            for(int j=1;j<=tot;j++)
                if (number[j]) status|=engineer[j];				//根据专家选取状态确定领域覆盖状态
            for(int j=1;j<=n;j++)
                if ((status&project[j])==project[j]) ST[j].push_back(i);	//通过交集比较确定当前状态是否能够完成项目j
            dp[1][i]=(status&project[1])==project[1];
        }
        int status1,status2,Less;
        for(int i=2;i<=n;i++)
        {
            memcpy(dp[i],dp[i-1],sizeof(dp[i]));				//对于大部分状态，直接从前一位转移过来
            for(int j=0,sz=ST[i].size();j<sz;j++)				//枚举能够完成项目i的状态
                for(int k=0;k<sz;k++)
                {
                    status1=ST[i][j];						//status1表示新的状态，即上面说的s
                    status2=ST[i][k];						//status2表示状态差，即上面说的s-x
                    if (status2&(~status1)) continue;				//判断status2是否是status1的子集
                    Less=(~status2)&status1;					//Less表示上一个状态，即上面说的x
                    dp[i][status1]=max(dp[i][status1],dp[i-1][Less]+1);		//状态转移
                }
        }
        int ans=0;
        for(int i=0;i<(1<<m);i++)
            ans=max(dp[n][i],ans);
        printf("Case #%d: %d\n",++tt,ans);
    }
    return 0;
}