http://acm.hdu.edu.cn/showproblem.php?pid=1011&PHPSESSID=nrt5ggjfqbhpk9au99mgcvm226
树形DP
题意:给你一颗树,n个顶点,n-1条边,m个花费,从根(编号1)出发,每个顶点有一定花费也有一定收获,并且经过的边不能再次经过,求最大收获是多少?
典型的树形DP,dp[root][k]表示以root为根的子树花费k得到的最大收获,则转移方程为:
dp[root][k]=max(dp[root][k],dp[root][k-i]+dp[t][i])(t为以root的子节点)
注意特判m=0的情况(直接输出0)
1 // #pragma comment(linker, "/STACK:102400000,102400000") 2 #include <cstdio> 3 #include <iostream> 4 #include <cstring> 5 #include <string> 6 #include <cmath> 7 #include <set> 8 #include <list> 9 #include <map> 10 #include <iterator> 11 #include <cstdlib> 12 #include <vector> 13 #include <queue> 14 #include <stack> 15 #include <algorithm> 16 #include <functional> 17 using namespace std; 18 typedef long long LL; 19 #define ROUND(x) round(x) 20 #define FLOOR(x) floor(x) 21 #define CEIL(x) ceil(x) 22 const int maxn = 110; 23 const int maxm = 210; 24 const int inf = 0x3f3f3f3f; 25 const LL inf64 = 0x3f3f3f3f3f3f3f3fLL; 26 const double INF = 1e30; 27 const double eps = 1e-6; 28 const int P[4] = {0, 0, -1, 1}; 29 const int Q[4] = {1, -1, 0, 0}; 30 const int PP[8] = { -1, -1, -1, 0, 0, 1, 1, 1}; 31 const int QQ[8] = { -1, 0, 1, -1, 1, -1, 0, 1}; 32 33 struct Edge 34 { 35 int u, v; 36 int next; 37 } edge[maxm]; 38 int head[maxn]; 39 int en; 40 void addsubedge(int u, int v) 41 { 42 edge[en].u = u; 43 edge[en].v = v; 44 edge[en].next = head[u]; 45 head[u] = en++; 46 } 47 void addedge(int u, int v) 48 { 49 addsubedge(u, v); 50 addsubedge(v, u); 51 } 52 struct Node 53 { 54 int n, p; 55 } node[maxn]; 56 bool vis[maxn]; 57 int dp[maxn][maxn]; 58 int n, m; 59 void init() 60 { 61 memset(head, -1, sizeof(head)); 62 en = 0; 63 memset(vis, 0, sizeof(vis)); 64 memset(dp, 0, sizeof(dp)); 65 } 66 void input() 67 { 68 for (int i = 1; i <= n; i++) 69 scanf("%d%d", &node[i].n, &node[i].p); 70 for (int i = 0; i < n - 1; i++) 71 { 72 int u, v; 73 scanf("%d%d", &u, &v); 74 addedge(u, v); 75 } 76 } 77 void dfs(int s) 78 { 79 vis[s] = 1; 80 int num = ceil((double)node[s].n / 20.0); 81 for (int i = num; i <= m; i++) 82 dp[s][i] = node[s].p; 83 for (int i = head[s]; i != -1; i = edge[i].next) 84 { 85 int v = edge[i].v; 86 if (vis[v]) continue; 87 dfs(v); 88 for (int j = m; j >= num; j--) 89 { 90 for (int k = 1; j + k <= m; k++) 91 { 92 dp[s][j + k] = max(dp[s][j + k], dp[s][j] + dp[v][k]); 93 } 94 } 95 } 96 } 97 void debug() 98 { 99 // 100 } 101 void solve() 102 { 103 dfs(1); 104 } 105 void output() 106 { 107 printf("%d\n", dp[1][m]); 108 } 109 int main() 110 { 111 // std::ios_base::sync_with_stdio(false); 112 #ifndef ONLINE_JUDGE 113 freopen("in.cpp", "r", stdin); 114 #endif 115 116 while (~scanf("%d%d", &n, &m)) 117 { 118 if (n == -1 && m == -1) return 0; 119 init(); 120 input(); 121 if (m == 0) 122 { 123 puts("0"); 124 continue; 125 } 126 solve(); 127 output(); 128 } 129 return 0; 130 }