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

Hint

Source

​​2016 CCPC-Final ​​

        看到資料範圍這麼的小，想了想搜尋還是差了一點，于是就隻能是狀壓了……

        大緻題意是，有n個項目，每個項目都涉及到一些領域，然後有m個專家，每個專家也都精通一些領域。規定每個專家隻能參與一個項目，可以在一個項目中負責多個領域，然後每個項目一定得保證所有的領域至少都有一個人精通才能完成。問最後最多能夠完成多少個項目。

#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;
}