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.
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)
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
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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <queue>
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<Node> map[];
int dp[][]; // dp[i][j] 从i出发又返回i，最大花费为j时所取得的价值
int val[], mark[]; int bfs(int s, int e)
{
int dist[], f[];
for (int i = ; i < ; ++i)
dist[i] = INF;
f[s] = -;
dist[s] = ;
queue<int> q;
q.push(s);
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = ; 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 != -; i = f[i])
mark[i] = ;
return dist[e];
} void dfs(int u, int pre, int mval)
{
dp[u][] = val[u];
for (int i = ; 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 >= ; --j)
for (int k = ; k <= j-*w; ++k)
if (dp[u][j-k-*w] != - && dp[y][k] != -)
dp[u][j] = max(dp[u][j], dp[y][k] + dp[u][j-k-*w]);
}
} int main()
{
int n, t;
while (scanf("%d %d", &n, &t) == )
{
memset(map, , sizeof(map));
memset(dp, -, sizeof(dp));
memset(mark, , sizeof(mark)); int a, b, c;
for (int i = ; 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 = ; i <= n; ++i)
scanf("%d", &val[i]); int tt = bfs(, n);
if (tt > t)
{
printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");
continue;
}
for (int i = ; i <= n; ++i)
if (mark[i])
dfs(i, -, t - tt); int dp2[], tmax = t - tt;
memset(dp2, -, sizeof(dp2));
dp2[] = ;
for (int i = ; i <= n; ++i)
{
if (!mark[i])
continue;
for (int j = tmax; j >= ; --j)
{
for (int k = ; k <= j; ++k)
if (dp2[j-k] != - && dp[i][k] != -)
dp2[j] = max(dp2[j], dp2[j-k] + dp[i][k]); }
}
int ans = ;
for (int i = ; i <= tmax; ++i)
if (ans < dp2[i])
ans = dp2[i];
printf("%d\n", ans);
}
return ;
}