好贷网好贷款

hdu 3586 Information Disturbing(树形dp + 二分)

发布时间:2016-12-3 23:57:23 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 3586 Information Disturbing(树形dp + 二分)",主要涉及到hdu 3586 Information Disturbing(树形dp + 二分)方面的内容,对于hdu 3586 Information Disturbing(树形dp + 二分)感兴趣的同学可以参考一下。

本文出自   http://blog.csdn.net/shuangde800  题目链接:   hdu-3586 题意    给一棵n个节点的树,节点编号为1~n,根节点为1。每条边有权值,砍掉一条边要花费cost(w)    要砍掉一些边, 使得每个叶子节点无法走到根节点。    要求砍掉花费总和不能超过m的情况下,让每条边花费上限尽量低 思路    二分可以砍的边的权值上限,然后树形dp    f[i]: 表示让i子树所有的叶子节点无法到达i点的最小花费    f[i] = sum { min(w(i,v), f[v]) | v是i的儿子节点 }    而这题有一个上限权值,即权值大于上限的就不能去砍。    所以上面的转移要改一下    if (w(i, v) > 上限) f[i] += f[v];    else  f[i] += min(w(i,v), f[v]);    然后,如果f[1]<=m,那么这个上限就符合条件    这一题,如果用INF初始化的话,那么INF一定要大于m的最大值1000000 代码

上一篇:netstat命令及日志分析命令
下一篇:think in java interview-高级开发人员面试宝典(二)

相关文章

相关评论