The Ghost Blows Light
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1567 Accepted Submission(s): 484
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)
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
Source
Recommend
liuyiding
题意：给你两个数n, T。 表示有n个房间， 和时间T.
然后有n - 1条无向边， a, b, c 表示 a 与 b 的距离是 c
然后有n个数字， 表示每个房间的宝藏数量。
问从房间1出发， 到房间n出去。 问能拿到多少宝藏。 如果出不出就输出 “……”;
思路： 树形DP
由于是一颗树， 每两个节点只有唯一路径， 所以要先把1~n的路径先搜索出来， 然后把边都赋值为0， 宝藏都赋值为0。
然后再树形DP。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
//树形DP
const int V = 100 + 50;
const int MaxN = 500 + 5;
const int mod = 1000000000 + 7;
int n, T, pri[V], Map[V][V], sum_path;
int dp[V][MaxN];// dp[i][j] 表示 第i个房间花费j时间能拿到的最大的宝藏
bool visit[V];
void dfs(int index) {
visit[index] = true;
for(int i = 1; i <= n; ++i)
if(!visit[i] && Map[index][i] >= 0) {
dfs(i);
for(int j = T; j >= Map[index][i] * 2; --j)
for(int k = 0; k <= j - Map[index][i] * 2; ++k)
dp[index][j] = max(dp[index][j], dp[index][j - Map[index][i] * 2 - k] + dp[i][k] + pri[i]);
}
}
bool dfs_path(int index, int len, int p) {
visit[index] = true;
if(index == n) {
pri[index] = 0;
sum_path = p;
T -= len;
return true;
}
for(int i = 1; i <= n; ++i)
if(!visit[i] && Map[index][i] > 0) {
if(dfs_path(i, len + Map[index][i], p + pri[i])) {
Map[index][i] = Map[i][index] = 0;
pri[index] = 0;
return true;
}
}
return false;
}
int main() {
int i, j;
while(~scanf("%d%d", &n, &T)) {
memset(Map, -1, sizeof(Map));
memset(dp, 0, sizeof(dp));
memset(visit, false, sizeof(visit));
sum_path = 0;
for(i = 0; i < n - 1; ++i) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
Map[a][b] = c;
Map[b][a] = c;
}
for(i = 1; i <= n; ++i)
scanf("%d", &pri[i]);
dfs_path(1, 0, pri[1]);
if(T < 0)
printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");
else {
memset(visit, false, sizeof(visit));
dfs(1);
printf("%d\n", dp[1][T] + sum_path);
}
}
}