BNUOJ 26283 The Ghost Blows Light

The Ghost Blows Light

Time Limit: 1000ms

Memory Limit: 32768KB

This problem will be judged on HDU. Original ID: 4276
64-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.

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

Sample Output

Source

2012 ACM/ICPC Asia Regional Changchun Online

解题：树形dp...此题要求从1 入从N出，由于是树，故只有一条路径从1通往N.只需要求出这题路径上的时间和，并且将时间置为0.然后在总时间中减去这部分时间再进行dp.为什么要求和呢？首要原因是判断能否活命！人为财死，鸟为食亡。

有人去求最短路！我只想说，只有一条路径，求最短路有意义吗？

如果这题路径上的时间和比给出的时间还大，必死无疑！为什么要置0呢？因为这部分的时间是必须要花掉的！！！！！不然还活不活啊？置零后减去就好了！由于不需花费时间，这些边，根据dp的设计，这些路径上的财富一定会被拿掉的！因为一直取max啊！不要任何消耗就能更大！有点贪心啊

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <climits>

 #include <vector>

 #include <queue>

 #include <cstdlib>

 #include <string>

 #include <set>

 #include <stack>

 #define LL long long

 #define INF 0x3f3f3f3f

 using namespace std;

 const int maxn = ;

 struct arc {

     int to,w;

 };

 int dp[maxn][],val[maxn],n,t,sum;

 vector<arc>g[maxn];

 bool dfs1(int u, int fa){

     if(u == n) return true;

     for(int i = ; i < g[u].size(); i++){

         if(g[u][i].to == fa) continue;

         if(dfs1(g[u][i].to,u)){

             sum += g[u][i].w;

             g[u][i].w = ;

             return true;

         }

     }

     return false;

 }

 void dfs(int u,int fa) {

     for(int i = ; i <= t; i++) dp[u][i] = val[u];

     for(int v = ; v < g[u].size(); v++) {

         if(g[u][v].to == fa) continue;

         dfs(g[u][v].to,u);

         int cost = *g[u][v].w;

         for(int j = t; j >= cost; j--){

             for(int k = ; k <= j - cost; k++)

                 dp[u][j] = max(dp[u][j],dp[u][j-k-cost]+dp[g[u][v].to][k]);

         }

     }

 }

 int main() {

     int u,v,w,i;

     while(~scanf("%d %d",&n,&t)) {

         for(i = ; i <= n; i++)

             g[i].clear();

         for(i = ; i < n; i++) {

             scanf("%d %d %d",&u,&v,&w);

             g[u].push_back((arc) {v,w});

             g[v].push_back((arc) {u,w});

         }

         for(i = ; i <= n; i++)

             scanf("%d",val+i);

         memset(dp,,sizeof(dp));

         sum = ;

         dfs1(,-);

         if(sum > t){

             puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!");

             continue;

         }

         t -= sum;

         dfs(,-);

         cout<<dp[][t]<<endl;

     }

     return ;

 }

巴特西