关于 「2012 年国家集训队互测」Tree 问题的回答

liu_cheng_ao 2018-09-19 16:29:34 2019-09-18 23:21:32

刚刚机房同学又发现了一本通的错误,作为最早接受在 LOJ 上放置一本通题目者,我对自己的鲁莽与不负责任感到无比懊悔与自责。首先在这里向全体与这本书和题目斗智斗勇的维护组成员们和「付费审稿员」用户们道歉。LibreOJ 确应有自己的精神,而不能只对一篇目录和摘要做出决定。

不过在讨论版上看到一篇文章《实际上 数据是有问题的》,这可不能怪一本通了,其中存在诸多问题,特在此进行一些讨论。

首先,这道题的题目、解法和数据均无错误

上述帖子的所有讨论其实都有一些问题。当然,会出现这样的问题,也和原题题解的证明不尽清晰有关。在此重新叙(扫)述(盲)。

首先要知道此题的解法:设 F(x) 表示当白边为 x 条时,最小生成树的权值,则在定义域内 \Delta F(x) 单调递增(或者说, F(x)-F(x-1) \le F(x+1)-F(x) ),即为一个凸函数,那么所有的函数值均位于凸包上,则可二分斜率以切凸包的方法来找到 F(need) 。(即著名的凸优化,亦有人称 wqs 二分)

wqs.png

像这样:我们设直线的斜率为 k ,那么给每条白边附加 k 的权值,得到的方案即切凸包所得的点(因为变换权值后,切点位置是最优的)。

这大约就是算法的基本情况。数学推导可以参见[2]。~~但[2]的证明未说明函数为凸(即「引理 2」中所指的,最小合法白边数之区间是否连续),可能造成误导。此处给出证明:~~但其对凸性的证明未写清楚,这里解释得详细一些。

假设 F 不是凸的,即存在一个 x 满足 F(x)-F(x-1) > F(x+1)-F(x) ,则考虑令 k=\frac{f(x+1)-f(x-1)}{2} ,即取过 (x-1,F(x-1)), (x+1,F(x+1)) 的直线,令白边 i 的权值为 w_i+k ,黑边保持不变,设新的权值为 w'

假设 F 不是凸的,就有某条直线切 F 于两点,即 \exists x,y,z,k 满足:设 F'(x)=F(x)+kx ,则 x<y<z, F'(x)=F'(z)=\min_{t} F'(t), F(y) > \frac{(z-y)F(x)+(y-x)F(z)}{z-x} ,则考虑令白边 i 的权值为 w_i+k ,黑边保持不变,设新的权值为 w'

根据 F 的假设,此时,存在两棵白边数分别为 x-1 x+1 的最小生成树,不妨设为 T_1, T_2

根据 F 的假设,此时,存在两棵白边数分别为 x z 的最小生成树,不妨设为 T_1, T_2

那么,我们按 w' 将两棵树的并的边分类,令权值相等者为一类。根据 Kruskal 算法的引理,在两棵树中,同类边对点的连通性相同,但由于抽屉原理,存在某类边中 T_2 的白边比 T_1 多,在这类边中必然存在一条 T_2 的白边 e_w 其两端在 T_1 中至少跨越了一条黑边 e_b ,将 T_1 e_b 替换为 e_w 即可得到一棵 x 条白边的最小生成树。

那么,我们按 w' 将两棵树的并的边分类,令权值相等者为一类。根据 Kruskal 算法的引理,在两棵树中,同类边对点的连通性相同,但由于抽屉原理,存在某类边中 T_2 的白边比 T_1 多,在这类边中必然存在一条 T_2 的白边 e_w 其两端在 T_1 中至少跨越了一条黑边 e_b ,将 T_1 e_b 替换为 e_w 即可得到一棵 x+1 条白边的最小生成树。对 z-x 归纳即可得到所有 y(x<y<z) 条边的最小生成树,自然也包括假设中的 y 。([2]的引理 2)

这棵生成树的边权为 \frac{F(x-1)+F(x+1)}{2} ,小于原来的最小生成树,矛盾。故 F 是凸的。

这棵生成树的边权为 \frac{(z-y)F(x)+(y-x)F(z)}{z-x} ,小于原来的最小生成树,矛盾。故 F 是凸的。

由此我们还能看出该性质对所有拟阵均成立:对于拟阵 M = (U, \mathcal{I}) ,将 U 中的元素染为黑白二色并赋权,设 F(x) 表示具有 x 个白色元素的最大权独立集之权值,则 F 为凸函数。

二分图不是拟阵!(不过 k 条白边的二分图匹配也满足这个性质)

当然, F 并不是严格凸的,存在 F(x)-F(x-1) = F(x+1)-F(x) 的情况,但这些点构成了一段区间([2] 引理 2)的直线,我们在计算生成树时优先选取黑边(相当于,令白边权值加上一个足够小的数)即可得到最小的白边数(端点),再计算直线上的函数值即可。所以代码中减去的是 need 位置而非二分出的端点。

参考我的代码

**这种方法应该相当普及,所以你们啊,还是要学习一个,不能总想弄个大新闻,把题目批判一番。**这篇帖子明显地没有清楚认识自己的算法,提出的只可称之为启发式的疑问,凭此为据贸然断定题目错误,而既无反例的证据,又无数理的论证,且未查证相关资料,实有失科学之精神。望诸君自勉。

UPD 2019.9.18

刚刚偶然翻回这篇帖子,发现好多错误……特此更正。

主要的错误:

  1. 原证明过程中的两棵生成树不一定是最小生成树。(这种情况下要证明中间存在某棵不大于中值的生成树不像文中那么容易)
  2. 匹配不是拟阵。

谢罪,谢罪。等我学到更多凸优化,再偶然看到这篇,我就来补充一下更归纳的内容。

共 4 条回复

liu_cheng_ao

我觉得没必要考虑它的实际意义,因为要是有实际意义的话,凸性就也有实际意义了。

GodWrath

想问一下, 为什么"我们设直线的斜率为 kkk,那么给每条白边附加 kkk 的权值,得到的方案即切凸包所得的点", 以及想知道切点直线方程的实际意义?

NyarukosanWoW

虽然没看懂楼主老师的数学证明(我很菜),不过今天思考了一个小时最终大概想通了,还是感谢管理员陪我们怼一本通,那本书能坑到连着两页打错字

Ez3real

这里是原文章作者 已删除

当时做题的时候半天没有A掉非常暴躁,于是在大胆猜想加并没有小心求证的时候在loj发了一篇帖子

深刻认识到了自己的错误

向被我浪费了很多时间的管理员@HeRaNO表示歉意

很感谢loj管理员可以让我知道我的错误并仔细讲解

向被我这个菜鸡浪费了时间和精力的loj管理员道歉

我错了 对不起大家

以后做事,定当三思而后行