poj 1463 树形dp入门

很简单的树形dp题目，转移方程是：

dp[u][0] += dp[v][1];
dp[u][1] += min( dp[v][0], dp[v][1] );

其中u是v的父亲节点。

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 using namespace std;
 6 
 7 const int N = 1500;
 8 bool flag[N];
 9 int head[N];
10 int dp[N][2];
11 int e, n;
12 
13 void init()
14 {
15     e = 0;
16     memset( flag, true, sizeof(flag) );
17     memset( head, -1, sizeof(head) );
18 }
19 
20 struct Edge
21 {
22     int v, next;
23 } edge[N];
24 
25 void addEdge( int u, int v )
26 {
27     edge[e].v = v;
28     edge[e].next = head[u];
29     head[u] = e++;
30 }
31 
32 void dfs( int u )
33 {
34     dp[u][0] = 0;
35     dp[u][1] = 1;
36     for ( int i = head[u]; i != -1; i = edge[i].next )
37     {
38         int v = edge[i].v;
39         dfs(v);
40         dp[u][0] += dp[v][1];
41         dp[u][1] += min( dp[v][0], dp[v][1] );
42     }
43 }
44 
45 int main ()
46 {
47     while ( scanf("%d", &n) != EOF )
48     {
49         init();
50         for ( int i = 0; i < n; i++ )
51         {
52             int u, v, m;
53             scanf("%d:(%d)", &u, &m);
54             while ( m-- )
55             {
56                 scanf("%d", &v);
57                 addEdge( u, v );
58                 flag[v] = false;
59             }
60         }
61         int root;
62         for ( int i = 0; i < n; i++ )
63         {
64             if ( flag[i] )
65             {
66                 root = i;
67                 break;
68             }
69         }
70         dfs(root);
71         int ans = min( dp[root][0], dp[root][1] );
72         printf("%d
", ans);
73     }
74     return 0;
75 }

也可以用二分图来做。