[2016CCPC 网络预选赛] HDU5834 记忆化搜索

题意

给一棵树，每个结点有宝贝，通过每条路要付费，问从每个点出发的最大收益。

思路

宝贝只能拿一次，边每次过都要交费。一个点的最大收入显然就是去几个路费小的子树拿宝贝，然后走一条不归路。那么就来两遍搜索，第一遍回溯每个子树回与不回的最大收益，第二遍把父亲方向回与不回的情况传下去，计算答案。

这里比较难处理的就是第二次搜索下传的时候，第一次统计当前子树不回的最优值是从下传的路径上来的，所以第一遍搜索额外要记录不回的次优值。如果没有次优值，那么就要用回的值来下传作为补丁，补根的情况。

自我感觉代码挺清晰的，赛场上一次就过了。

AC代码 C++

#include <stdio.h> #include <vector> #include <algorithm> using namespace std; #define MAXN 100005 struct edge { int v, c; edge(int vv = 0, int cc = 0) : v(vv), c(cc) {} }; vector<edge>G[MAXN]; int v[MAXN]; int ans[MAXN]; int dp[MAXN][3]; int b[MAXN]; pair<int, int> dfs1(int u, int fa, int c) { int i, hui = 0, f = 0, s = -0x3f3f3f3f; pair<int, int> tmp; dp[u][0] = v[u]; for (i = G[u].size(); i--;) { edge& e = G[u][i]; if (e.v != fa) { tmp = dfs1(e.v, u, e.c); if (tmp.first) dp[u][0] += tmp.first; if (tmp.second > f) { s = f; f = tmp.second; b[u] = e.v; } else if (tmp.second > s) s = tmp.second; } } dp[u][1] = dp[u][0] + f; dp[u][2] = s ? dp[u][0] + s : 0; return pair<int, int>(max(dp[u][0] - (c << 1), 0), max(dp[u][1] - c, 0) - max(dp[u][0] - (c << 1), 0)); } void dfs2(int u, int fa, pair<int, int> rec) { int i; pair<int, int> down; ans[u] = max(dp[u][0] + rec.second, dp[u][1] + rec.first); for (i = G[u].size(); i--;) { edge& e = G[u][i]; if (e.v != fa) { down.first = rec.first + dp[u][0] - max(dp[e.v][0] - 2 * e.c, 0) - 2 * e.c; down.second = 0; down.second = max(down.first - rec.first + rec.second + e.c, down.second); down.first = max(down.first, 0); if (b[u] != e.v) down.second = max(rec.first + dp[u][1] - max(dp[e.v][0] - 2 * e.c, 0) - e.c, down.second); else if (dp[u][2]) down.second = max(rec.first + dp[u][2] - max(dp[e.v][0] - 2 * e.c, 0) - e.c, down.second); else down.second = max(rec.first + dp[u][0] - max(dp[e.v][0] - 2 * e.c, 0) - e.c, down.second); dfs2(e.v, u, down); } } } int main() { int T, t, n, u, vv, c, i; scanf("%d", &T); for (t = 1; t <= T; t++) { printf("Case #%d:\n", t); scanf("%d", &n); for (i = 1; i <= n; i++) { scanf("%d", v + i); G[i].clear(); b[i] = -1; } for (i = 1; i<n; i++) { scanf("%d%d%d", &u, &vv, &c); G[u].push_back(edge(vv, c)); G[vv].push_back(edge(u, c)); } dfs1(1, 0, 0); dfs2(1, 0, pair<int, int>(0, 0)); for (i = 1; i <= n; i++) printf("%d\n", ans[i]); } return 0; }