k条白边最小生成树问题
k条白边最小生成树问题
问题
给定一张图,每条边都有一个权值和颜色,仅为黑色或白色,求一条恰好包含 条白边的最小生成树。
求解
这个问题与分数规划问题非常类似
给每条白边的权值都增加 ,二分 ,求此时的最小生成树总权值 ,并求出这个树包含几条白边。
假如包含的白边数 ,则增大 ,否则减小 ,直到 ,则最小生成树的总权值则为
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Ender's Blog!
评论
给定一张图,每条边都有一个权值和颜色,仅为黑色或白色,求一条恰好包含 条白边的最小生成树。
这个问题与分数规划问题非常类似
给每条白边的权值都增加 ,二分 ,求此时的最小生成树总权值 ,并求出这个树包含几条白边。
假如包含的白边数 ,则增大 ,否则减小 ,直到 ,则最小生成树的总权值则为