洛谷P2619 [国家集训队]Tree I

can can need?一道很好的二分题目,阐释了进阶的二分思想的运用,扩展了原本二分局限的思想. 原本我一直认为二分都是一些满足单调性的东西,虽然这个题也确实是,但是它的单调性其实是比较模糊的。 求最小生成树,但是要求白边的边数一定是 n e e d need need情况下的. 考虑下二分出这个 c o s t cost cost,接下来是检验能否在指定的 c o s t cost cost内,是否能找到 n e e d 条白边 need条白边 need条白边, n − 1 − n e e d n-1-need n−1−need条黑边的生成树. 然后我就又又又没有思路,以上仍然是胡编乱造的,去看题解了. 原来我理解错题目的意思了,意思 首先对原始的边进行Kruskal，随便跑出一个MST,假设有 x x x条白边. 接下来对 x x x讨论,如果 x > n e e d x>need x>need,证明白边的边权是比较小的,我们需要把一些白边替换成黑边,如何替换呢,我们考虑整体把原本白色的边的边权稍加修改,如果 x > = n e e d x>=need x>=need,说明白边比较多,考虑把它扔到后边 把边权整体加上 y 把边权整体加上y 把边权整体加上y.反之,如果 x < n e e d x