BZOJ 2654 tree


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2654

题意:边有黑有白,求白边数恰好为 need 的最小生成树数量...


直接搞是无法满足白边数目的,怎么办呢?我们考虑到一条边权值越大“越不容易”被选到,对于整个白边边集也是这样的。如果为全体白边增加边权\(\Delta \),显然选择白边的数量是单调不降的,所以可以二分,但是有一个小问题,就是可能 need 无法被二分到,这是因为有一些重复边权我们选择了黑边,在排序时将颜色作为第二关键字,先选白边即可

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 2654 tree


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,