省选算法学习笔记

· · 个人记录

wqs 二分

P2619 [国家集训队] Tree I

本题更像是普通二分。因为选择白边的数量 f(add) 和每条白边边权增加值 add 是单调变化的。但由于它是 wqs 本人引用的例子，还是在此说明。

解决一个小疑问：为什么可以整数二分？为什么不存在这种情况：

求证：每条白边增加值为 i 或 i+1 时，所求的 MST 边权和都和实际要求的答案相同。

证明：考虑设白边边权增加值为 i 时，MST 的白边数量 f(i)\in[l_i,r_i]，白边边权增加值为 i+1 时，白边数量为 f(i+1) \in [l_{i+1},r_{i+1}]。

之所以 f(i) 在一个区间内浮动，是因为 r_i-l_i 条白边的边权 w 加上 i 后，恰好等于某些黑边的边权 b。

于是一个显然的性质是：虽然 f(i)\in[l_i,r_i]，但是这些情况下计算出 MST 的边权和大小是相同的。因为毕竟只是把相同边权的白边换成黑边而已，不改变边权和。

则原问题等价于证明 l_i\le r_{i+1}，这样子所有 [l_i,r_i] 拼接起来是连续的，就能覆盖所有白边数量的值域。

考虑设原来的 r_i 条边的边集为 S_i，原来的 l_i 的边集为 SS_i，新的 r_{i+1} 条边的边集为 S_{i+1}，新的 l_{i+1} 的边集为 SS_{i+1}。

显然 S_{i+1}\subset S_i，SS_{i+1} \subset SS_i。因为有些边原来 \in S_{i}，但边权 +1 后就 \notin S_{i+1} 了。而另外有些边原来 \in SS_i ，后来 \in S_{i+1} 了。

我们考虑哪些边原来 \in S_i ，但后来 \notin S_{i+1}。这些边就是那些原来边权为 w+i ，等于某些黑边边权 b 的边，因为 w+i>b 的边一定满足 w+(i+1)\ge b ，即这些边一定 \in S_{i+1} 。所以 r_i-r_{i+1} 的数量等于原来边权为 w+i ，等于某些黑边边权 b 的边的数量，也即 r_i-r_{i+1}=r_i-l_i，所以 r_{i+1}=l_i。命题得证。

所以在 [l_i,r_i] 处和 [l_{i+1},r_{i+1}] 得到的答案相同？但这显然是错误的！因为这样的话，按照前面的性质无论 i 取多少，MST 边权和都变成一样的了！所以说 [l,r] 区间拼接起来是非连续的？那么如何保证 need 属于某个区间呢？