本文共 2842 字，大约阅读时间需要 9 分钟。
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 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 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_JUDGE113 freopen("in.cpp", "r", stdin);114 #endif115 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 }
转载于:https://www.cnblogs.com/xysmlx/p/3535923.html
