poj2441 Arrange the Bulls

思路：
状态压缩dp。需要一点优化，否则容易超时。
实现：
 1 #include <cstdio>
 2 #include <vector>
 3 #include <cstring>
 4 #include <iostream>
 5 using namespace std;
 6 vector<int> G[21];
 7 int n, m, dp[1 << 21];
 8 int main()
 9 {
10     int p, x;
11     scanf("%d%d", &n, &m);
12     for (int i = 1; i <= n; i++)
13     {
14         scanf("%d", &p);
15         for (int j = 0; j < p; j++)
16         {
17             scanf("%d", &x);
18             G[i].push_back(x);
19         }
20     }
21     dp[0] = 1;
22     for (int i = 0; i < n; i++)
23     {
24         for (int j = (1 << m + 1) - 1; j >= 0; j--)
25         {
26             if (__builtin_popcount(j) != i) continue;
27             for (int k = 0; k < G[i + 1].size(); k++)
28             {
29                 int tmp = G[i + 1][k];
30                 if (!(j >> tmp & 1)) dp[j | 1 << tmp] += dp[j];
31             }
32         }
33     }
34     int cnt = 0;
35     for (int j = 0; j < (1 << m + 1) - 1; j++) 
36         if (__builtin_popcount(j) == n) cnt += dp[j];
37     printf("%d
", cnt);
38     return 0;
39 }