学习笔记--APIO 2018 二分专题 By wuvin

2021-04-11 13:25

阅读：552

题解by wuvin：

如果我们对所有白色边的边权增加\(M*maxW\),那么最小生成树会得到一个白色边尽量少的方案。

如果我们对所有白色边的边权增加\(-M*maxW\),那么最小生成树会得到一个白色边尽量多的方案。

我们定义这个给白色边的额外权值为C。随着C从小到大遍历\([-M \times maxW,M \times maxW]\)，那么我们的最优方案中的白色边会逐渐减少。

如果某个C下，我们最优方案刚好得到K条边，那么这就是原题的最优解。因为最终代价为原题的最优解+\(C*K\) 其中K和C都是常数，所以说最优解和原题是同一个最优解。

所以我们可以二分C值，然后使用\(kruskal\)生成树即可。（假设白色边和黑色代价一样的时候选择白色边）

但是注意一个细节，随着C的增加，白色边边数只是单调不增而已，可能出现C=1是得到5条白色边，C=1+eps是就是3条白色边，这是因为可能存在可以代替白色边的权值刚好之比白色边大1的黑色边。

所以二分到最后需要特判一下。

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：学习笔记--APIO 2018 二分专题 By wuvin
文章链接：http://soscw.com/index.php/essay/74276.html

亲，登录后才可以留言！