POJ -- 2436

Disease Management

Description

Alas! A set of D (1 <= D <= 15) diseases (numbered 1..D) is running through the farm. Farmer John would like to milk as many of his N (1 <= N <= 1,000) cows as possible. If the milked cows carry more than K (1 <= K <= D) different diseases among them, then the milk will be too contaminated and will have to be discarded in its entirety. Please help determine the largest number of cows FJ can milk without having to discard the milk.

Input

* Line 1: Three space-separated integers: N, D, and K

* Lines 2..N+1: Line i+1 describes the diseases of cow i with a list of 1 or more space-separated integers. The first integer, d_i, is the count of cow i's diseases; the next d_i integers enumerate the actual diseases. Of course, the list is empty if d_i is 0.

Output

* Line 1: M, the maximum number of cows which can be milked.

Sample Input

Sample Output

5

思路：需要用到位运算，D最为16,用一个int数（32位 > 16位，足够表示）的每个二进制位表示病毒的存在与否，1为存在，0不存在，这样复杂度为2^16*n(通过剪枝实际达不到这么大)，可以接受。因此有两种方法解本题，（1），dfs,枚举D的k-组合。（2），通过二进制枚举D的k-组合。
用dfs，最后程序跑得时间是32ms，二进制枚举跑得时间是285ms，如此大的差距，原因就是二进制把所有组合都枚举完了，其中包含很多冗余状态，说白了就是大爆力。

DFS版：（32ms）

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<string>
 6 #include<algorithm>
 7 #define MAXN 1111
 8 using namespace std;
 9 int cow[MAXN],vis[MAXN],N,D,K,ans;
10 void dfs(int idx,int cnt,int sum){
11     if(cnt == K){
12         int num = 0;
13         for(int i = 0;i < N;i ++)
14             if(cow[i] == (cow[i] & sum)) num++;
15         ans = max(ans,num);
16         return;
17     }
18     for(int i = idx;i < D;i ++){
19         if(!vis[i]){
20             vis[i] = 1;
21             dfs(i+1,cnt+1,sum|(1 << i));
22             vis[i] = 0;
23         }
24     }
25 }
26 int main(){
27     int tmp,kind;
28 //    freopen("in.c","r",stdin);
29     while(~scanf("%d%d%d",&N,&D,&K)){
30         memset(cow,0,sizeof(cow));
31         memset(vis,0,sizeof(vis));
32         for(int i = 0;i < N;i ++){
33             scanf("%d",&tmp);
34             for(int j = 0;j < tmp;j ++){
35                 scanf("%d",&kind);
36                 cow[i] |= (1 << (kind-1));
37             }
38         }
39         ans = 0;
40         dfs(0,0,0);
41         printf("%d
",ans);
42     }
43     return 0;
44 }

二进制枚举版：（285ms）

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<string>
 6 #include<algorithm>
 7 #define MAXN 1111
 8 using namespace std;
 9 int cow[MAXN];
10 int count_digit(int n){
11     int cnt = 0;
12     for(int  i = 0;i < 32;i ++)
13         if(n & (1 << i)) cnt ++;
14     return cnt;
15 }
16 int main(){
17     int n,m,k,tmp,kind;
18     //freopen("in.c","r",stdin);
19     while(~scanf("%d%d%d",&n,&m,&k)){
20         memset(cow,0,sizeof(cow));
21         for(int i = 0;i < n;i ++){
22             scanf("%d",&tmp);
23             for(int j = 0;j < tmp;j ++){
24                 scanf("%d",&kind);
25                 cow[i] |= (1 << (kind-1));
26             }
27         }
28         int ans = 0;
29         for(int i = 0;i < (1 << m);i ++){
30             int sum = 0,cnt = 0;
31             if(count_digit(i) > k) continue;
32             for(int j = 0;j < n;j ++)
33                 if((cow[j] | i) == i) cnt++;
34             ans = max(ans,cnt);
35         }
36         printf("%d
",ans);
37     }
38     return 0;
39 }