思路：對每一條邊涂上顏色1或-1，顏色值加到關聯的兩個點上，則一種成功的方案必須滿足最后每個點的值為0.

剪枝：統計出和某個點i相關聯的邊的個數，如果枚舉到某一條邊的時候發現：abs(sum[i]) > degree[i]，則剪去，其中sun[i]表示i點的值，degree[i]表示剩下的還沒有枚舉的和i關聯的邊的個數。

1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 6 const int N = 9; 7 const int M = 28; 8 int sum[N]; 9 int degree[N]; 10 int n, m, ans; 11 12 struct Edge 13 { 14 int u, v; 15 } edge[M]; 16 17 int judge() 18 { 19 for ( int i = 1; i <= n; i++ ) 20 { 21 if ( sum[i] ) return 0; 22 } 23 return 1; 24 } 25 26 int abs( int x ) 27 { 28 return x > 0 ? x : -x; 29 } 30 31 void dfs( int cur ) 32 { 33 if ( cur == m ) 34 { 35 ans += judge(); 36 return ; 37 } 38 for ( int i = 1; i <= n; i++ ) 39 { 40 if ( abs(sum[i]) > degree[i] ) return ; 41 } 42 int u = edge[cur].u, v = edge[cur].v; 43 degree[u]--; 44 degree[v]--; 45 sum[u]++; 46 sum[v]++; 47 dfs( cur + 1 ); 48 sum[u]--; 49 sum[v]--; 50 sum[u]--; 51 sum[v]--; 52 dfs( cur + 1 ); 53 sum[u]++; 54 sum[v]++; 55 degree[u]++; 56 degree[v]++; 57 } 58 59 int main () 60 { 61 int t; 62 scanf("%d", &t); 63 while ( t-- ) 64 { 65 scanf("%d%d", &n, &m); 66 memset( degree, 0, sizeof(degree) ); 67 for ( int i = 0; i < m; i++ ) 68 { 69 scanf("%d%d", &edge[i].u, &edge[i].v); 70 degree[edge[i].u]++; 71 degree[edge[i].v]++; 72 } 73 bool flag = false; 74 for ( int i = 1; i <= n; i++ ) 75 { 76 if ( degree[i] & 1 ) 77 { 78 flag = true; 79 break; 80 } 81 } 82 ans = 0; 83 if ( !flag ) 84 { 85 memset( sum, 0, sizeof(sum) ); 86 dfs(0); 87 } 88 printf("%d\n", ans); 89 } 90 return 0; 91 }

?

轉載于:https://www.cnblogs.com/huoxiayu/p/4671757.html

總結

以上是生活随笔為你收集整理的hdu 5305 回溯+剪枝的全部內容，希望文章能夠幫你解決所遇到的問題。

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