k条白边最小生成树问题

问题

给定一张图，每条边都有一个权值和颜色，仅为黑色或白色，求一条恰好包含 $k$ 条白边的最小生成树。

求解

这个问题与分数规划问题非常类似

给每条白边的权值都增加 $C$ ，二分 $C$ ，求此时的最小生成树总权值 $w$ ，并求出这个树包含几条白边。

假如包含的白边数 $r > k$ ，则增大 $C$ ，否则减小 $C$ ，直到 $r = k$ ，则最小生成树的总权值则为 $w - k * C$