c/c++语言开发共享cfE. Ehab and a component choosing problem(贪心)

题意 “题目链接” 给出一棵树,每个节点有权值,选出$k$个联通块,最大化 $$frac{sum_{i in S} a_i}{k}$$ Sol 结论:选出的$k$个联通块的大小是一样的且都等于最大联通块的大小 证明:因为我们是在保证分数最大的情况下才去最大化$k$,一个很经典的结论是单独选择一 …


题意

题目链接

给出一棵树,每个节点有权值,选出(k)个联通块,最大化

[frac{sum_{i in s} a_i}{k}]

sol

结论:选出的(k)个联通块的大小是一样的且都等于最大联通块的大小

证明:因为我们是在保证分数最大的情况下才去最大化(k),一个很经典的结论是单独选择一个权值最大的联通块得到的分数一定是最大的,然后我们这时我们才去考虑最大化(k)

那么思路就很清晰了,先一遍dfs dp出最大联通块,然后再一遍dfs从下往上删就行了

%ignore_pre_1%

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ctvol.com/c-cdevelopment/606084.html

(0)
上一篇 2021年5月13日
下一篇 2021年5月13日

精彩推荐