# Poj Solution 2441

```http://poj.org/problem?id=2441

//* @author:
/*
����:
N��ţ��M�������(barn)��ÿ��ţ���м����Լ�ϲ����barn��Ҫ��Ϊÿ��ţ����һ��barn��
ʹ��ÿ��ţ��ֵ���barn�����Լ�ϲ���ģ���ÿ��barn�v�ֻ������һ��ţ����Ϸ��ķ��䷽��������N,M<=20��

����:
��һ����N��M(1<=N<=20, 1<=M<=20);
����4��N��:
��i�еĵ�һ�������ǵ�i��ţϲ����barn��,���������ǵ�i��ţϲ����barn���(1<=i<=N)
���:
���䷽��������
*/
import java.util.*;
public class Main
{
static final int N=20+2;
static final int M=1<< 20+1;

public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n, m, p;
int mat[][]=new int[N][N];
int dp[][]=new int[2][M];
int i, k, j, next;
n=sc.nextInt();
m=sc.nextInt();
for (i = 1; i <= n; i++)
{
p=sc.nextInt();
while ((p--)!=0)
{
k=sc.nextInt();
mat[i][k] = 1;
}
}

int s = 0;
dp[s][0] = 1;
for (i = 1; i <= n; i++)
{
for (j = 0; j < (1 << m); j++)
{
if (dp[s][j]!=0)
{
for (k = 1; k <= m; k++)
{
if (mat[i][k] == 1)
{
next = j | (1 << (k - 1));
if (next != j)      // ��k��barnû��ռ��
dp[(s + 1) % 2][next] += dp[s][j];
}

}
dp[s][j] = 0;
}
}

s = (s + 1) % 2;
}
int sum = 0;
for (i = 0; i < (1 << m); i++) sum += dp[s][i];
System.out.printf("%dn", sum);
}
}
```
This entry was posted in poj. Bookmark the permalink.