首页 > 代码库 > HDU 4276 - The Ghost Blows Light
HDU 4276 - The Ghost Blows Light
The Ghost Blows Light
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3345 Accepted Submission(s): 1040
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
题意：
有一棵树，有n个节点，每个节点有一个权值，每一条边有一个时间，在经过的时间不超过给定时间m的情况下，求从1点到n点的路径的最大权值
思路：
对于一棵树只有一条 从根节点到某节点的最短路，所以先判断这条最短路是不是符合条件，符合的话，把这条路上的点记为0，然后就是树形DP求解，
因为要走其他点，必须再回来，所以回来时要乘以二所经过的路径
这是个背包问题：
状态转移方程为，dp[i][j]=max(dp[i][j],dp[i][k]+dp[i][j-2*val-k])
AC代码：
1 # include <bits/stdc++.h> 2 using namespace std; 3 4 const int MAX = 120; 5 struct node 6 { 7 int to; 8 int next; 9 int t;10 }tree[MAX];11 int head[MAX];12 int tol = 0;13 int w[MAX];14 int n, t;15 int Mint;16 int dp[MAX][600];17 18 void add(int a, int b, int val)19 {20 tree[tol].to = b;21 tree[tol].next = head[a];22 tree[tol].t = val;23 head[a] = tol++;24 }25 26 bool dfs1(int root, int f)27 {28 if(root == n)29 return true;//找到了30 for(int i = head[root]; i != -1; i = tree[i].next)31 {32 int son = tree[i].to;33 if(son == f)34 continue;35 if(dfs1(son, root))36 {37 Mint += tree[i].t;38 tree[i].t = 0;39 return true;40 }41 }42 return false;43 }44 45 void dfs2(int root, int f)46 {47 for(int i = 0; i <= t; i++)48 dp[root][i] = w[root];49 for(int i = head[root]; i != -1; i = tree[i].next)50 {51 int son = tree[i].to;52 if(son == f)53 continue;54 dfs2(son, root);55 int cost = tree[i].t * 2;56 for(int j = t; j >= cost; j--)57 {58 for(int k = 0; k <= j - cost; k++)59 dp[root][j] = max(dp[root][j], dp[root][j - k - cost] + dp[son][k]);60 }61 }62 }63 int main()64 {65 while(scanf("%d%d", &n, &t) != EOF)66 {67 memset(head, -1, sizeof(head));68 memset(dp, 0, sizeof(dp));69 tol = 0;70 Mint = 0;71 int a, b, val;72 for(int i = 1; i < n; i++)73 {74 scanf("%d%d%d", &a, &b, &val);75 add(a, b, val);76 add(b, a, val);77 }78 for(int i = 1; i <= n; i++)79 {80 scanf("%d", &w[i]);81 }82 dfs1(1, -1);// 看看直接走去的最短时间是多少，83 if(Mint > t)84 {85 printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");86 continue;87 }88 t -= Mint;89 dfs2(1, -1);90 printf("%d\n", dp[1][t]);91 }92 return 0;93 }
HDU 4276 - The Ghost Blows Light
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。