HDU - 3586 Information Disturbing——树形dp

HDU - 3586 Information Disturbing——树形dp

题意有点绕，就不再说明了

普通的树形dp没想出状态转移方程， 所以考虑二分求解，算了算复杂度也可以接受

二分limit，可以想到limit越大求出的总和只会更小，所以二分的序列是递减的，问题就转化成了在一个递减序列中求出第一个小于等于m的位置，因为要求的是第一个位置，所以结果是左界，然后控制一下大于小于等于号就行了。

然后就是如何根据一个已知的limit求出最小的总和（删除的所有边的权值总和），这个要用到树形dp，不是很难想，具体参考代码。但是边界问题不太好处理，对于dp[u] += dp[v],  如果dp[v]是INF的话应该直接把dp[u]赋值为INF然后break

#include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 1010;int n, m, tot, head[maxn], dp[maxn], minv, maxv;struct Edge { int to, cost, next;}edge[maxn<<1];void init() { tot = 0; memset(head, -1, sizeof(head)); minv = INF, maxv = 0;}void addedge(int u, int v, int cost) { ++tot; edge[tot].to = v, edge[tot].cost = cost, edge[tot].next = head[u]; head[u] = tot;}void dfs(int u, int limit) { if (head[u] == -1) { dp[u] = INF; return; } for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to, cost = edge[i].cost; dfs(v, limit); if (cost <= limit) dp[u] += min(dp[v], cost); else { if (dp[v] == INF) { dp[u] = INF; break; } else dp[u] += dp[v]; } }}int solve() { int l = minv, r = maxv; while (l <= r) { int mid = (l + r)>>1; memset(dp, 0, sizeof(dp)); dfs(1, mid); if (dp[1] > m) l = mid + 1; else r = mid - 1; } return l <= maxv ? l : -1;}int main() { while (~scanf("%d %d", &n, &m) && n && m) { init(); int u, v, cost; for (int i = 1; i <= n - 1; i++) { scanf("%d %d %d", &u, &v, &cost); addedge(u, v, cost); minv = min(minv, cost); maxv = max(maxv, cost); } printf("%d\n", solve()); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。