bzoj2809: [Apio2012]dispatching

2021-07-20 02:21

阅读：477

http://www.lydsy.com/JudgeOnline/problem.php?id=2809

领导关系形成一棵树，那么答案为$ans=max{L[u]\times k}$,其中k代表以u为根的子树中选出的节点数个数(设这些节点为$v_1,v_2\cdots v_k$且有$\sum_{i=1}^{k}C[v_i]\leq M$。

每个节点建一个大根堆，维护薪水值。初始时若自己满足条件就选自己，否则不选。从叶子节点往上推，对于每个节点，将它与它的儿子节点合并。如果当前的选择费用超出了M，就pop出堆里的最大的，一直到不超过M为止，用左偏树维护就行。动态维护当前选择的节点数num和选择费用sum即可。

上一篇：JSON

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：bzoj2809: [Apio2012]dispatching
文章链接：http://soscw.com/essay/106436.html

亲，登录后才可以留言！