Problem Description
My name is Hu Bayi, robing an ancient tomb in Tibet. The tomb consists of N rooms (numbered from 1 to N) which are connected by some roads (pass each road should cost some time). There is exactly one route between any two rooms, and each room contains some treasures. Now I am located at the 1st room and the exit is located at the Nth room. Suddenly, alert occurred! The tomb will topple down in T minutes, and I should reach exit room in T minutes. Human beings die in pursuit of wealth, and birds die in pursuit of food! Although it is life-threatening time, I also want to get treasure out as much as possible. Now I wonder the maximum number of treasures I can take out in T minutes.
Input
There are multiple test cases. The first line contains two integer N and T. (1 <= n <= 100, 0 <= T <= 500) Each of the next N - 1 lines contains three integers a, b, and t indicating there is a road between a and b which costs t minutes. (1<=a<=n, 1<=b<=n, a!=b, 0 <= t <= 100) The last line contains N integers, which Ai indicating the number of treasure in the ith room. (0 <= Ai <= 100)
Output
For each test case, output an integer indicating the maximum number of treasures I can take out in T minutes; if I cannot get out of the tomb, please output "Human beings die in pursuit of wealth, and birds die in pursuit of food!".
Sample Input
5 10 1 2 2 2 3 2 2 5 3 3 4 3 1 2 3 4 5
Sample Output
11
思路
1. 经典树形 DP 题目
2. 动规数组定义: dp[i][j] 表示从节点 i 出发使用最大花费为 j 后重新回到节点 i 能够得到的最大价值
3. 状态转移方程: dp[i][j] = dp[c1][k1] + dp[c2][k2] + ... + dp[cn][kn], c1, c2 ... cn 为节点 i 的孩子, k1, k2 ... kn 是在其对应的孩子节点分配的时间,
k1+k2+...kn <= j
4. 盗贼必须要跑出去, 因此最短路径上的时间需要预支. 以最短路径上的点(u)为树根求出以 u 为根的树分配 j 时间能够得到的最大收益 dp[u][j]
5. 然后再计算, 如何在最短路径上的节点分配时间使总收益最大, 这也是一步 DP, 具体来说, 这依然是一步树形 DP
6. 实现分为 3 部分, 第一部分使用 BFS(bellmanford, dijkstra) 算出最短路径的耗费以及最短路径上的所有点; 第二部分是 (4); 第三部分是 (5)
代码 from kedebug
#include#include #include #include #include using namespace std;#define max(a,b) (((a) > (b)) ? (a) : (b))const int INF = 1e9;struct Node { int y, w; Node(int _y, int _w) : y(_y), w(_w) { }};vector map[110];int dp[110][510]; // dp[i][j] 从i出发又返回i，最大花费为j时所取得的价值int val[110], mark[110];int bfs(int s, int e){ int dist[110], f[110]; for (int i = 0; i < 110; ++i) dist[i] = INF; f[s] = -1; dist[s] = 0; queue q; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < map[u].size(); ++i) { Node &v = map[u][i]; if (dist[v.y] > dist[u] + v.w) { f[v.y] = u; dist[v.y] = dist[u] + v.w; q.push(v.y); } } } for (int i = e; i != -1; i = f[i]) mark[i] = 1; return dist[e];}void dfs(int u, int pre, int mval){ dp[u][0] = val[u]; for (int i = 0; i < map[u].size(); ++i) { int y = map[u][i].y; int w = map[u][i].w; if (y == pre || mark[y]) continue; dfs(y, u, mval); for (int j = mval; j >= 0; --j) for (int k = 0; k <= j-2*w; ++k) if (dp[u][j-k-2*w] != -1 && dp[y][k] != -1) dp[u][j] = max(dp[u][j], dp[y][k] + dp[u][j-k-2*w]); }}int main(){ int n, t; while (scanf("%d %d", &n, &t) == 2) { memset(map, 0, sizeof(map)); memset(dp, -1, sizeof(dp)); memset(mark, 0, sizeof(mark)); int a, b, c; for (int i = 1; i < n; ++i) { scanf("%d %d %d", &a, &b, &c); map[a].push_back(Node(b, c)); map[b].push_back(Node(a, c)); } for (int i = 1; i <= n; ++i) scanf("%d", &val[i]); int tt = bfs(1, n); if (tt > t) { printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n"); continue; } for (int i = 1; i <= n; ++i) if (mark[i]) dfs(i, -1, t - tt); int dp2[510], tmax = t - tt; memset(dp2, -1, sizeof(dp2)); dp2[0] = 0; for (int i = 1; i <= n; ++i) { if (!mark[i]) continue; for (int j = tmax; j >= 0; --j) { for (int k = 0; k <= j; ++k) if (dp2[j-k] != -1 && dp[i][k] != -1) dp2[j] = max(dp2[j], dp2[j-k] + dp[i][k]); } } int ans = 0; for (int i = 0; i <= tmax; ++i) if (ans < dp2[i]) ans = dp2[i]; printf("%d\n", ans); } return 0;}