题目的介绍以及思路完全参考了下面的博客：http://blog.csdn.net/acm_cxlove/article/details/7964739
做这道题主要是为了加强自己对SPFA的代码的训练以及对树dp的一些思路的锻炼。我特地研究了一下树dp的部分
|
1
2
3
4
5 |
for
(int i = t; i >= w; i--){ for
(int j = i-w; j >= 0; j--){ dp[u][i] = max(dp[u][i], dp[u][j]+dp[v][i - j - w]); } } |
循环里面是不能搞错顺序的，外层的i逆序显然，但为什么里层会有问题呢？ 因为w是可以＝0的，这个时候想像一下，如果j=i-w的话，那么就会有
dp[u][i]=max(dp[u][i],dp[u][i]+dp[v][i-j-w])，但是dp[u][i]是已经更新了的，所以这样会出错，两层循环都必须要逆序。
下面贴一记代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108 |
#pragma warning(disable:4996)#include<iostream>#include<cstring>#include<string>#include<cstdio>#include<algorithm>#include<cmath>#include<vector>#include<queue>#define maxn 150using
namespace std;struct
Edge{ int
u, v, w; Edge(){} Edge(int
ui, int
vi, int
wi) :u(ui), v(vi), w(wi){}}e[2*maxn];int
n, t;int
val[maxn];int
ecnt;int
first[maxn], nxt[2 * maxn];void
add(int
u, int
v, int
w){ e[ecnt].u = u; e[ecnt].v = v; e[ecnt].w = w; nxt[ecnt] = first[u]; first[u] = ecnt++;}int
dis[maxn], vis[maxn];int
p[maxn];void
spfa(int
s){ memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); memset(p, -1, sizeof(p)); queue<int> que; que.push(s); vis[s] = 1; dis[s] = 0; while
(!que.empty()) { int
u = que.front(); que.pop(); vis[s] = 0; for
(int i = first[u]; i != -1; i = nxt[i]){ int
v = e[i].v; if
(dis[v] > dis[u] + e[i].w){ dis[v] = dis[u] + e[i].w; p[v] = i; if
(!vis[v]){ que.push(v); vis[v] = 1; } } } }}int
dp[maxn][550];void
dfs(int
u, int
fa){ for
(int i = first[u]; i != -1; i = nxt[i]){ int
v = e[i].v, w = e[i].w * 2; if
(v == fa) continue; dfs(v, u); for
(int i = t; i >= w; i--){ for
(int j = i-w; j >= 0; j--){ dp[u][i] = max(dp[u][i], dp[u][j]+dp[v][i - j - w]); } } } for
(int i = 0; i <= t; i++){ dp[u][i] += val[u]; }}int
main(){ while
(cin >> n >> t) { int
ui, vi, wi; memset(first, -1, sizeof(first)); ecnt = 0; for
(int i = 0; i < n - 1; i++){ scanf("%d%d%d", &ui, &vi, &wi); add(ui, vi, wi); add(vi, ui, wi); } for
(int i = 1; i <= n; i++) scanf("%d", val + i); spfa(1); if
(dis[n]>t) { puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!"); continue; } for
(int i = n; i != 1; i = e[p[i]].u){ e[p[i]].w = e[p[i] ^ 1].w = 0; } t -= dis[n]; memset(dp, 0, sizeof(dp)); dfs(1, -1); printf("%d\n", dp[1][t]); } return
0;} |
HDU4276 The Ghost Blows Light SPFA&&树dp
原文：http://www.cnblogs.com/chanme/p/3567172.html