思路：

狀態壓縮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\n", cnt); 38 return 0; 39 }

?

轉載于:https://www.cnblogs.com/wangyiming/p/9141724.html

總結

以上是生活随笔為你收集整理的poj2441 Arrange the Bulls的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。