总结
1. dp[u][k] 是恰好用完 k 时间的最大价值
2. dfs(u, pre, vmax) 是计算 dp[u][1...vmax] 的值
3. dfs 内部遍历, j 从大到小, 防止重复计算 f(j) = g(j-k)
而 k 是从小到大, 因为在 134 行, dp[j] = max(dp[j], dp[j-k]+dp'[k]) 比较特殊, k 可以等于 0. 导致 dp[j] 被重复计算
代码
/* * source.cpp * * Created on: Apr 6, 2014 * Author: sangs */#include#include #include #include #include #include #include #include #include using namespace std;class Road {public: int to, cost; Road(int _to, int _cost):to(_to), cost(_cost) {} Road() { to = cost = 0; } bool operator <(const Road &rhs) const { return this->cost < rhs.cost; }};vector graph[1000];int val[1000];int dp[1000][1000];const int INF = 0X3F3F3F3F;int dist[1000];int father[1000];bool mark[1000]; // mark those nodes must passbool visited[1000];/* * calculate the shortest path from 1 to n * as well as those nodes in shortest path * SPFA algorithm */int bfs(int n) { queue record; memset(visited, 0, sizeof(visited)); memset(mark, 0, sizeof(mark)); memset(dist, 0x3f, sizeof(dist)); record.push(1); dist[1] = 0; father[1] = -1; while(!record.empty()) { int thisNode = record.front(); record.pop(); for(size_t i = 0; i < graph[thisNode].size(); i ++) { int j = graph[thisNode][i].to; //cout << j << " " << dist[i] << " " << graph[thisNode][i].cost << endl; if(dist[thisNode] + graph[thisNode][i].cost < dist[j]) { dist[j] = dist[thisNode] + graph[thisNode][i].cost; father[j] = thisNode; record.push(j); } } } for(int i = n; i != -1; i = father[i]) { mark[i] = 1; } return dist[n];}/* * tree_dp to calculate dp[u][1...vmax] * dp[u][k] is the maximum income when assigned k time to node u and get back to u * pre is u's father */void tree_dp(int u, int pre, int vmax) { dp[u][0] = val[u]; for(size_t i = 0; i < graph[u].size(); i ++) { // enum v's child int index = graph[u][i].to; if(index == pre) continue; if(mark[index]) continue; tree_dp(index, u, vmax); int cost = graph[u][i].cost; for(int j = vmax; j >= 0; j --) { for(int k = 0; k <= j-2*cost; k ++) { dp[u][j] = max(dp[u][j], dp[u][j-k-2*cost]+dp[index][k]); } } }}int main() { freopen("input.txt", "r", stdin); int n, T; while(scanf("%d%d", &n, &T) != EOF) { for(int i = 0; i <= n+10; i ++) graph[i].clear(); for(int i = 0; i < n-1; i ++) { int from, to, cost; scanf("%d%d%d", &from, &to, &cost); graph[from].push_back(Road(to, cost)); graph[to].push_back(Road(from, cost)); } for(int i = 1; i <= n; i ++) scanf("%d", val+i); int cutTime = bfs(n); T -= cutTime; memset(dp, 0, sizeof(dp)); dp[n+1][0] = 0; for(int i = 1; i <= n; i ++) { if(mark[i] == 0) continue; tree_dp(i, n+1, T); for(int j = T; j >= 0; j --) { for(int k = 0; k <= j; k ++) { //for(int k = j; k >= 0; k --) { dp[n+1][j] = max(dp[n+1][j], dp[n+1][j-k] + dp[i][k]); } } } int res = 0; for(int i = 0; i <= T; i ++) res = max(res, dp[n+1][i]); printf("%d\n", res); } return 0;}