POJ 2342 Anniversary party

树形DP入门啦。
View Code
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 using namespace std;
 6 
 7 int n,len;
 8 int dp[6001][2];
 9 int value[6001];
10 bool flag[6001];
11 vector <int> G[6001];
12 
13 int max(int a,int b)
14 {
15     if(a > b)   return a;
16     return b;
17 }
18 
19 void init()
20 {
21     int i;
22     for(i = 0;i <= n;i++)
23         G[i].clear();
24     memset(dp,0,sizeof(dp));
25     memset(flag,true,sizeof(flag));
26 }
27 
28 void dfs(int v)
29 {
30     for(vector<int>::size_type i = 0;i < G[v].size();i++)
31     {
32         int u = G[v][i];//u是v的儿子节点
33         dfs(u);
34         dp[v][0] += max(dp[u][0],dp[u][1]);
35         dp[v][1] += dp[u][0];
36     }
37     dp[v][1] += value[v];
38 }
39 
40 int main()
41 {
42     int boss;
43     scanf("%d",&n);
44     init();
45     for(int i = 1;i <= n;i++)
46         scanf("%d",&value[i]);
47     int p,q;
48     while(scanf("%d%d",&p,&q),p + q != 0)
49     {
50         G[q].push_back(p);
51         flag[p] = false;
52     }
53 
54     for(int i = 1;i <= n;i++)
55     {
56         if(flag[i])
57         {
58             boss = i;
59             break;
60         }
61 
62     }
63     dfs(boss);
64 
65     int ans = max(dp[boss][1],dp[boss][0]);
66     printf("%d\n",ans);
67 
68     return 0;
69 }