POJ - 2441 Arrange the Bulls (状态压缩DP)

Arrange the Bulls

Time Limit: 4000MS	Memory Limit: 65536K
Total Submissions: 4458	Accepted: 1695

Description

Farmer Johnson's Bulls love playing basketball very much. But none of them would like to play basketball with the other bulls because they believe that the others are all very weak. Farmer Johnson has N cows (we number the cows from 1 to N) and M barns (we number the barns from 1 to M), which is his bulls' basketball fields. However, his bulls are all very captious, they only like to play in some specific barns, and don’t want to share a barn with the others. 

So it is difficult for Farmer Johnson to arrange his bulls, he wants you to help him. Of course, find one solution is easy, but your task is to find how many solutions there are. 

You should know that a solution is a situation that every bull can play basketball in a barn he likes and no two bulls share a barn. 

To make the problem a little easy, it is assumed that the number of solutions will not exceed 10000000.

Input

In the first line of input contains two integers N and M (1 <= N <= 20, 1 <= M <= 20). Then come N lines. The i-th line first contains an integer P (1 <= P <= M) referring to the number of barns cow i likes to play in. Then follow P integers, which give the number of there P barns.

Output

Print a single integer in a line, which is the number of solutions.

Sample Input

3 4
2 1 4
2 1 3
2 2 4
      

Sample Output

4      

题意:有n头牛，每头牛有自己喜欢住的屋子，问使所有牛都住上自己喜欢的屋子有几种可能      

直接状态压缩，注意几个问题:      

1.从上一状态转换过来的必须满足二进制1的个数正好为已经选好位置的人的个数      

2.从上一个状态转换过来的还要满足当前选择的位置没有被选中      

3.最终得到结果则是需要判断二进制1的个数为n，将他们求和即可      

其中求解二进制1中的个数有两种比较快的方法      

1.自己写函数      

while(x > 0){num ++; x &= x(x - 1)}      

num即二进制1的个数      

2.用系统给予的函数      

__builtin_popcount(x)      

/*头文件模板*/

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <cctype>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iomanip>
#include <typeinfo>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define pb push_back
#define mp make_pair
#define mem(a, x) memset(a, x, sizeof(a))
#define copy(a, b) memcpy(a, b, sizeof(a))
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid + 1, r
#define FIN freopen("input.txt", "r", stdin)
#define FOUT freopen("output.txt", "w", stdout)

typedef long long LL;
typedef pair<int, int > PII;
typedef pair<int, string> PIS;
typedef pair<LL, LL>PLL;
typedef unsigned long long uLL;

template<typename T>
void print (T* p, T* q, string Gap = " ", bool flag = false) {
	int d = p < q ? 1 : -1;
	while (p != q) {
		if (flag) cout << Gap[0] << *p << Gap[1];
		else cout << *p;
		p += d;
		if (p != q && !flag) cout << Gap;
	}
	cout << endl;
}

template<typename T>
void print (const T &a, string bes = "") {
	int len = bes.length();
	if (len >= 2) cout << bes[0] << a << bes[1] << endl;
	else cout << a << endl;
}

template<typename T>
void debug (T* p, T* q, string Gap = " ", bool flag = false) {
#ifndef ONLINE_JUDGE
	int d = p < q ? 1 : -1;
	cout << "Debug out : ";
	while (p != q) {
		if (flag) cout << Gap[0] << *p << Gap[1];
		else cout << *p;
		p += d;
		if (p != q && !flag) cout << Gap;
	}
	cout << endl;
#endif
}

template<typename T>
void debug (const T &a, string bes = "") {
#ifndef ONLINE_JUDGE
	int len = bes.length();
	cout << "Debug out : ";
	if (len >= 2) cout << bes[0] << a << bes[1] << endl;
	else cout << a << endl;
#endif
}

void IO_Init() {
	ios::sync_with_stdio (false);
}

LL LLabs (const LL a) {
	return a >= 0 ? a : -a;
}

const double PI = 3.1415926535898;
const double eps = 1e-10;
const int MAXM = 1e5 + 5;
const int MAXN = 2e6 + 5;
const int INF = 0x3f3f3f3f;

/*头文件模板*/

int d[25][25], dp[(1 << 20) + 5];
int n, m, s;
int getb(int x) {
	int ret = 0;
	while(x) {
		x &= x - 1;
		ret ++;
	}
	return ret;
}

int main() {
#ifndef ONLINE_JUDGE
	FIN;
	//FOUT;
#endif
	IO_Init();
	int x;
	while(~scanf("%d%d", &n, &m)) {
		mem(d, 0);
		mem(dp, 0);
		for(int i = 0; i < n; i ++) {
			scanf("%d", &s);
			for(int j = 0; j < s; j ++) {
				scanf("%d", &x);
				d[i][x - 1] = 1;
			}
		}
		for(int i = 0; i < n; i ++) {
			for(int j = 0; j < (1 << m); j ++) {
				if(getb(j) != i) continue;
				for(int k = 0; k < m; k ++) {
					if(d[i][k] && ~ j >> k & 1) {
						if(i != 0) {
							dp[j | 1 << k] += dp[j];
						} else {
							dp[j | 1 << k] = 1;
						}
					}
				}
			}
		}

		int ret = 0;
		for(int j = 0; j < (1 << m); j ++) {
			if(getb(j) == n) ret += dp[j];
		}
		printf("%d\n", ret);
	}
	return 0;
}