k条白边最小生成树问题

问题

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

求解

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

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

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