题目链接

传送门

Description

给你一个无向带权连通图,每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。
题目保证有解。

Input

第一行V,E,need分别表示点数,边数和需要的白色边数。
接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号),边权,颜色(0白色1黑色)。

Output

一行表示所求生成树的边权和。
V<=50000,E<=100000,所有数据边权为[1,100]中的正整数。

Sample Input

2 2 1

0 1 1 1

0 1 2 0

Sample Output

2

题解

这个题有个奇怪的做法。。
显然我们说白色边的边权越大 我们选的白色边越少
这样我们就可以二分啦!
我们二分给每条白色边增加的权值 然后跑最小生成树看看选的白色边是不是满足数量要求 然后总边权再减去增加的权值
但是你可能怀疑二分的正确性?即如果给白色边边权加上mid,则所选白色边>need,如果加上mid+1,则所选白色边<need。解决方法是,在排序的时候,我们将白色边放在相同长度的黑色边之前。这样,因为mid+1时白边<mid,所以一定有若干=mid的黑边。在mid时,我们多选的白边就可以被黑边替换掉。所以在最后统计答案的时候,只需要ans-=mid*need即可。
这样就搞定了

代码