CF141E Clearing Up 题解

▶

INFO 题意简述

给定一个 个点 条边的图，每个边分为黑边和白边，构造一组黑边个数等于白边个数的生成树或报告无解。

容易发现如果 是偶数，那么 就是奇数不可能平均分，此时应该报告无解。

我们给黑色边定价 白色边定价 。 我们希望求一颗权值恰好为 的生成树。

可以先求一次最大和最小生成树，如果这个区间并没有跨过 ，就直接报告无解。

考虑使用调整法构造出来一组解。取出最大生成树，抛弃所有不在树上的权值为正的边，只保留在最大生成树上的边，我们想将生成树的权值减到 。

考虑加入一条边对于权值的影响。加边后生成树会形成一个环。此时考虑删掉环上的最大边，由于边权只有 ，因此这部分就好处理很多。删掉环上任意一个正权边就会使得权值变小 ，没有正权边任意断掉一条则没有影响。实际上就是加入一条边后的 MST。

不难发现每次 MST 的权值最多减少 ，因为加入新的边之后权值如果变小，则必然包含了新加入的负权值的边（因为此时总共就 条边，剩下 条是上一轮的 MST），而我们上文已经得出加入负权边断开正权边最多使得权值变化 。

依次加入所有负权边之后就会变成全局最小值，因为此时已经加入了所有的负权边，而加入开始被抛弃的正权边之后并不会使得答案更优，因此此时相当于是全局 MST，因此在这个过程中 MST 的权值会取到最小权值和最大权值之间的所有偶数值。

但是依次加边复杂度是 的，不太能接受。注意到 MST 权值单调递减，二分变成 的位置即可。