The Ghost Blows Light
Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 427664-bit integer IO format: %I64d Java class name: Main
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
Sample Output
11
Source
解题：树形dp,反正到n的路上的时间都是必须花的，就把这条路上的时间一并搞掉
然后就是树形dp了
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 110; 4 struct arc { 5 int to,w,next; 6 arc(int x = 0,int y = 0,int z = -1) { 7 to = x; 8 w = y; 9 next = z; 10 } 11 } e[maxn*maxn]; 12 int head[maxn],dp[maxn][510],val[maxn],tot,sum,t,n; 13 void add(int u,int v,int w) { 14 e[tot] = arc(v,w,head[u]); 15 head[u] = tot++; 16 } 17 bool shortest(int u,int fa) { 18 if(u == n) return true; 19 for(int i = head[u]; ~i; i = e[i].next) { 20 if(e[i].to == fa) continue; 21 if(shortest(e[i].to,u)) { 22 sum += e[i].w; 23 e[i].w = e[i^1].w = 0; 24 return true; 25 } 26 } 27 return false; 28 } 29 void dfs(int u,int fa){ 30 for(int i = 0; i <= t; ++i) dp[u][i] = val[u]; 31 for(int i = head[u]; ~i; i = e[i].next){ 32 if(e[i].to == fa) continue; 33 dfs(e[i].to,u); 34 int cost = e[i].w<<1; 35 for(int j = t; j >= cost; --j) 36 for(int k = 0; k + cost <= j; ++k) 37 dp[u][j] = max(dp[u][j],dp[e[i].to][k] + dp[u][j - cost - k]); 38 } 39 } 40 int main() { 41 int u,v,w; 42 while(~scanf("%d%d",&n,&t)){ 43 memset(head,-1,sizeof head); 44 sum = tot = 0; 45 for(int i = 1; i < n; ++i){ 46 scanf("%d%d%d",&u,&v,&w); 47 add(u,v,w); 48 add(v,u,w); 49 } 50 memset(dp,0,sizeof dp); 51 for(int i = 1; i <= n; ++i) scanf("%d",val + i); 52 shortest(1,-1); 53 if(sum > t) { 54 puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!"); 55 continue; 56 } 57 t -= sum; 58 dfs(1,-1); 59 printf("%d ",dp[1][t]); 60 } 61 return 0; 62 }