hdu 5305 回溯+剪枝

思路：对每一条边涂上颜色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
", ans);
89     }
90     return 0;
91 }