首页 > 代码库 > hdu 4276(树形dp)

hdu 4276(树形dp)

2024-07-02 22:17:38   234人阅读

题意：带权树上有起点终点每个点上有宝藏，一个人只有T分钟要从起点到重点，问你最多能收集多少宝藏。

思路：树形dp，首先判断能不能走到终点，然后把路径上的边权变为0时间减去所有边权。dp[v][j]表示从v出发回到v话费j分钟最多能收集到的宝藏。

dp[v][j] = max(dp[v][j], dp[x][k] + dp[v][j-k-2*val]);

被G++卡了好长时间，换成c++就过了。

代码如下：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 #include <set>
 5 #include <iostream>
 6 #include <queue>
 7 #include <map>
 8 #include <math.h>
 9 #include <string>
10 #define MP(a, b) make_pair(a, b)
11 #define PB(a) push_back(a)
12 using namespace std;
13 
14 const int LEN = 101;
15 typedef pair<int, int> pii;
16 int n, m, dp[LEN][LEN*5], vex[LEN], tans;
17 vector<pii> Map[LEN];
18 
19 bool initdfs(int v, int fa){
20     if(v == n-1) return true;
21     for(int i=0; i<Map[v].size(); i++){
22         int x = Map[v][i].first;
23         if(x != fa){
24             if(initdfs(x, v)){
25                 tans += Map[v][i].second;
26                 Map[v][i].second = 0;
27                 return true;
28             }
29         }
30     }
31     return false;
32 }
33 
34 void dfs(int v, int fa){
35     for(int i=0; i<Map[v].size(); i++){
36         int x = Map[v][i].first, val = Map[v][i].second;
37         if(x != fa){
38             dfs(x, v);
39             for(int j=m; j>=0; j--){
40                 for(int k=0; k<=j-2*val; k++){
41                     dp[v][j] = max(dp[v][j], dp[x][k] + dp[v][j-k-2*val]);
42                 }
43             }
44         }
45     }
46     for(int i=0; i<=m; i++) dp[v][i] += vex[v];
47 }
48 
49 int main()
50 {
51 //    freopen("in.txt", "r", stdin);
52 
53     int a, b, c;
54     while(scanf("%d%d", &n, &m)!=EOF){
55         for(int i=0; i<LEN; i++) Map[i].clear();
56         memset(dp, 0, sizeof dp);
57         tans = 0;
58         for(int i=0; i<n-1; i++){
59             scanf("%d%d%d", &a, &b, &c);
60             a--, b--;
61             Map[a].PB(MP(b, c));
62             Map[b].PB(MP(a, c));
63         }
64         for(int i=0; i<n; i++){
65             scanf("%d", &vex[i]);
66         }
67         initdfs(0, -1);
68         if(tans > m){
69             puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!");
70             continue;
71         }
72         dfs(0, -1); 
73         int ans = 0;
74         for(int i=0; i<=m-tans; i++){
75             ans = max(ans, dp[0][i]);
76         }
77         printf("%d\n", ans);
78     }
79     return 0;
80 }
View Code

 


联系
我们