CF1163F 题解

· · 个人记录

本文尝试证明最多只取一条非树边（指均不被 1\leadsto i 的最短路树和 i\leadsto n 的最短路树包含）。

符号参考这个。

Lemma 3.2 以及之前毫无疑问是对的。

定义 T_1 表示以 D(1\leadsto i) 的最短路树，T_n 表示以 D(i\leadsto n) 的最短路树

对于任意一个点 p，考虑 pre(p) 和 suf (p) 之间的一些性质：

反证，设 id(suf(p))<id(pre(p))

记 D(1 \leadsto suf(p))=d,D(suf(a) \leadsto pre(p))=c,D(pre(p)\leadsto n)=e，D(suf(p)\leadsto p)=a,D(p\leadsto pre(p))=b。

那么显然 D(1\leadsto p)=D(1\leadsto suf(p))+D(suf(p)\leadsto pre(p))+D(pre(p)\leadsto p)=d+c+b，这是因为若两点在 T_1 上为祖先-儿子关系，那么他们在两点上的路径恰好就是两点的最短路。同理有 D(p \leadsto n)=a+c+e。

因为最短路的性质，有 D(1\leadsto p) \le D(1\leadsto suf(p)) + D(suf(p)\leadsto p)，D(p\leadsto n) \le D(p\leadsto pre(p))+D(pre(p))\leadsto n)，即 d+c+b\le d+a,a+c+e\le e+b，相加可得 a+b+2c+d+e\le a+b+d+e \to 2c\le 0，显然不合法。

为了区分，所有删边后的情况都加一个 '。

任取一条删边后的最短路 Q'，满足只有连续一段不在 P 上（记作 x\leadsto y，其中 x,y\in P）。我们假设至少存在两条非树边在 x\leadsto y 上。

Update，有简单证明：

考虑任意一条不经过 (P(i),P(i+1)) 的最短路径 Q，我取 Q 中第一个满足 id(suf(p))\ge id(P(i+1)) 的 p 以及他前面的点 q。显然 q 一定满足 id(pre(q))\le id(suf(q)) \le id(P(i))。因此我取 Q=1\leadsto pre(q) \leadsto q \to p\leadsto suf(p)\leadsto n 一定不会更劣，这是因为取的是最短路。

因此最多只有一条非树边。

先对每一条非树边进行考虑，假设当前考虑边 (a,b)，那么：

证明很简单：反证，若 id(pre(b)) \le id(P(i))，我们可以把 1\leadsto x\leadsto b 替换成 P(1\leadsto pre(b)\leadsto b)，由于后者是 1\leadsto b 的原图的最短路，所以一定不劣，并且这条非树边消失。

那么此时取最靠前的一条非树边 (a,b)，那么有 id(P(i+1))\le id(pre(b))\le id(suf(b))，那么我们把 b\leadsto y\leadsto n 替换成 P(b\leadsto suf(b) \leadsto n)，由于后者是原图的最短路，因此一定不劣。而此时只剩下了一条非树边。

证毕。

可以看出来，引用的博客应该是把最后一段的 suf 改成 pre 导致他显然地挂掉了。