贪心复习~(好像暴露了什么算法……)
『题意』
给出一棵以1为根的树,每条边有两个值:p-强度、w-重量。
对于给出的树,我们可以对每条边进行操作——将它的p、w同时减去相同的值,但是要求 $p\ge 0,w>0$ 。(注意只能减,不能加)
进行操作后,需要使原树满足:如果 u 是 v 的父亲,那么 u 到 v 的边的 p 不能小于 以 v 为根节点的子树中所有边的 w 之和。
求出一种方案,使得在满足条件的情况下,树的 w 之和最大,输出这个方案。如果不存在任何方案,输出-1(Of course 有 SPJ)
『解析』
简单地思考一下,对于这道题,叶子节点的p以及与根节点相连的边的w是没有用的……
根据这个我们可以想出一个思路——从下到上尽可能减去重量,求到重量最小的树;再从上到下贪心地尽可能给每条边加重量(不超过原重量),得到答案。比较有趣的是正解好像也是这么写的——因为按理来说样例的解很多,但是我的程序跑出来是一样的~
「减重量-DFS」
从根节点DFS到叶子节点,然后从叶子节点递归得到整个树的最小重量解(当然是唯一解)
声明一下变量:
(1) edg[i] 按照输入顺序给出的第i条边(从1开始);
(2) fedg[i] 对应edg[i],表示修改后的第i条边;
(3) pnt[i] 表示以i为根的子树的最小总重量(满足条件的);
(4) (u,v) 表示 u,v 之间的边在输入时的顺序
Tab. edg,fedg 都是结构体,包含元素 wgt,ref 分别表示重量、强度
假设现在是 u点,已经计算出它的儿子 v,边的编号 id=(u,v)。
首先判断重量是否合法——如果子树v的最小重量 pnt[v] 都大于 edg[id].ref 了,那么就不合法,输出-1。
否则,显然如果不考虑 $edg[id].wgt>0$ ,那么我们可以把 edg[id].ref 降至 pnt[v] —— 那么我们就是要在 $edg[id].wgt>0$ 的情况下尽可能的使 edg[id].ref 小。计算 $delta$ 表示将 edg[id] 的 wgt 和 ref 同时减去 delta。那么 $delta=min\{edg[id].ref-hvy , edg[id].wgt-1\}$,将削减后的值存入 fedg[id] ,最后统计 pnt[u] 。
这样我们就求出了最小重量的方案(同时判断了不存在解的情况)。
「增重量-Solve」
根据最开始的分析,我们可以将与根节点相连的所有边的 wgt 和 ref 都调至最大(也就是初始值)。
在 Solve() 函数中除了 当前节点u 还附带一个变量 $del$表示u的子树在最小基础下的能够增加的最大重量。其实Solve()的本质还是一个 DFS……但是它的返回值是 以u为根的子树中在最小重量的基础上新增加的重量之和,所以我们用deltot来记录这个返回值。
那么从根节点出发,我们可以把 del 看做是正无穷,因为没有任何限制。
假设现在正在处理 边(u,v) ,u是父亲。
如果当前边再加上 del 不超过原来的重量,那么就可以将它加上,返回 deltot+=del(这里del就相当于加重量的机会,而这种情况就相当于把所有机会用完了)。
否则在给当前边增加重量后,del还有剩余——那么就贪心地把 del 分配到 v 里去。也就是先给 边(u,v) 加大到可能的最大值,同时将 del 减去增加的值。但是我们不能直接将 del 下传到 v 去,因为可能 v 的子树在增加 del 的重量后,边(u,v) 的强度不够,所以下传时,我们进行一个处理—— $min(del,fedg[id].ref-pnt[v])$(这里的pnt[v]其实就是在未对v进行 Solve() 修改时的v的子树总重)。最后在 Solve() 返回时将 del 减去其返回值,表示用去了这么多“机会”。
然后就可以了~
『源代码』
1 | /*Lucky_Glass*/ |
The End
Thanks for reading!
Email: lucky_glass@foxmail.com ,欢迎提问~