【BZOJ2654】tree

今天LCF的考试题

听说是臭垃圾陈立杰的题

这题的思路很巧妙:二分一个数,让所有白边的权值减去这个数然后求最小生成树,如果得到的最小生成树所含白边少于\(need\)那么说明二分的数需要减小使白边能够更多地进入最小生成树,代价是之后加回来的权值更大。否则可以将二分的数减小或者不变。

这题还有一个小细节:如果减去某个数后有相同权值的白边和黑边,优先加白边。想想就明白了。

Subscribe
提醒
1 评论
最旧
最新 得票最多
Inline Feedbacks
View all comments
陈立杰
4 年 之前

乡巴佬