BZOJ 2654 tree

发布于 2017-06-22  212 次阅读


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

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


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

 


一个非常弱的准退役OIER