删边最短路问题

## 问题 给定**正权无向图** $G$，求其删掉每一条边之后的 $1$ 到 $n$ 最短路长度（保证存在）。 ## 做法 **注意，以下的做法如果改成有向图，就是错的！** 文末将给出一个反例，以及在哪一步证明证不下去了。 大多数的做法是这样的，任取某一条 $1$ 到 $n$ 的最短路，记为 $1\rightsquigarrow n$（令 $i\rightsquigarrow j$ 代表 $i$ 到 $j$ 的最短路，下同）。若边 $(i,j)$ 不在 $1\rightsquigarrow n$ 上，则显然最短路不会改变。所以只考虑 $1\rightsquigarrow n$ 上的边删去的效果。 我们考虑所有边 $(i,j)$，我们求出强制经过这条边 $(i,j)$ 的 $1$ 到 $n$ 的最短路，显然为了最短，是 $1\rightsquigarrow i \to j \rightsquigarrow n$。 之后，我们考虑某一条 $1\rightsquigarrow i \to j \rightsquigarrow n$ 与 $1\rightsquigarrow n$ 的交集 $I$，用 $\operatorname{len}(1\rightsquigarrow i \to j \rightsquigarrow n)$ 更新所有 $1\rightsquigarrow n$ 上不属于 $I$ 的边的答案（更新就是取 $\min$） 这个看上去有一定的道理，**我们相当于依次强制最短路走过每条其他的边，然后看这样形成的最短路径避开了 $1\rightsquigarrow n$ 上的哪些边，更新这些边的答案**。 但是这个做法有一个问题，我们怎么知道，强制 **一条边** 就够了呢，为什么不需要强制两条或者更多？注意到大部分题解并没有证明它的正确性，接下来我们证明它是对的。 ## 证明 我们令 $G$ 从 $1$ 出发的最短路树为 $S$（有多个则任取），考虑 $1\rightsquigarrow n$ 上任意一条边 $(i,j)$，显然 $i\to j$ 在 $S$ 中。 考虑 $j$ 为根的子树 $S_1$ ，令 $S$ 除去 $S_1$ 的部分为 $S_0$，我们首先知道 **$S_0$ 中的点 $u$，$1\rightsquigarrow u$ 不会变**。这是因为考虑 dijkstra 构造最短路树的过程，首先每个点 $1\rightsquigarrow x$ 不会变小，而 $S_0$ 中的点由于不在 $j$ 的子树内，所以不依赖于 $i\to j$ ，所以不会变大。不会变大变小，所以不变。 现在令 $G$ 从 $n$ 出发的最短路树为 $T$（有多个则任取），同样的，我们可以求得 $T_0,T_1$ 代表最短路树中不在 $i$ 的子树的和在 $i$ 的子树的。 令所有点构成的集合为 $V$，那么我们显然有 $S_0\cup S_1=T_0 \cup T_1=V$，且 $S_0\cap S_1=T_0\cap T_1=\varnothing$。 我们现在有一个非常重要的观察，**就是 $S_1\cap T_1=\varnothing$，或者说，没有任何一个节点 $u$ 在 $1$ 的最短路树上处于 $j$ 的子树内，也在 $n$ 的最短路树上处于 $i$ 的子树内**。 这个原因是假设存在这样的节点 $u$，考察 $1\rightsquigarrow u$，而 $u$ 在 $1$ 最短路树中处于 $j$ 的子树内，所以 $1\rightsquigarrow u=1\rightsquigarrow i \to j \rightsquigarrow u$，同理由于它也在 $n$ 的最短路树上属于 $i$ 的子树，$u\rightsquigarrow n=u \rightsquigarrow i \to j \rightsquigarrow n$。 这似乎还不能导出矛盾，那么我们把它和 $1\rightsquigarrow n$ 合在一起看呢？$1\rightsquigarrow n = 1\rightsquigarrow i \to j \rightsquigarrow n$。 $$\begin{matrix}&&&u&&&\\ & &\nearrow& &\nwarrow& & \\1& \rightsquigarrow & i& \to& j& \rightsquigarrow &n\end{matrix}$$ **（那两个斜着的箭头应该是弯的，但由于博客的限制打不出来）** 我们令 $\operatorname{len}(i\to j)=a$，$\operatorname{len}(i\rightsquigarrow u)=b$，$\operatorname{len}(j\rightsquigarrow u)=c$ 由于 $1\rightsquigarrow i \to j \rightsquigarrow u$ 是最短的，那么一定有 $\operatorname{len}(i \to j \rightsquigarrow u)\leq\operatorname{len}(i \rightsquigarrow u)$，这得出 $a+c\leq b$，同时 $u \rightsquigarrow i \to j \rightsquigarrow n$ 最短告诉我们 $a+b\leq c$。 二式相加，$2a\leq 0$，由于正权，矛盾。 所以说，$S_1\cap T_1=\varnothing$，**这告诉我们 $S_1 \subseteq T_0$**，这有何用？我们接着看。 考虑任意一条 $1\rightsquigarrow n$，它一定只经过 $S_0$ 内部的边， 两个节点分别属于 $S_0,S_1$ 的边，和都属于 $S_1$ 的边这三种。 首先，这条最短路径上必须至少有一条分别属于 $S_0,S_1$ 的边，因为 $1\in S_0,n\in S_1$。 取最后一条这样的边，设为 $(u,v)$，首先，这条最短路上 $v\rightsquigarrow n$ 中所有点均属于 $S_1$，而 $S_1\subseteq T_0$，$v\rightsquigarrow n$ 中所有点**都**属于 $T_0$，这说明 $v\rightsquigarrow n$ 中没有一条边是 $(i,j)$，且长度就是 $T$ 中 $v$ 的距离。 接下来考察 $u$，我们取 $S_0$ 树上的 $1\rightsquigarrow u$，它显然至少不长于我们取的这条最短路的 $1\to \cdots \to u$。所以说 $1\rightsquigarrow u\to v \rightsquigarrow n$ 不长于最短路，所以它与最短路等长。 同时，由于 $1\rightsquigarrow u$ 中每个点都属于 $S_0$，我们也可以导出它也不包含 $(i,j)$ 且长度就是 $S$ 中 $u$ 的距离。所以 $1\rightsquigarrow u\to v \rightsquigarrow n$ 不长于最短路且满足条件。 综上所述，一定存在一条 $(u,v)$ 满足： - $1\rightsquigarrow u\to v \rightsquigarrow n$ 与最短路等长。 - $1\rightsquigarrow u\to v \rightsquigarrow n$ 不经过 $(i,j)$ - $1\rightsquigarrow u$ 和 $v \rightsquigarrow n$ 的长度不被 $(i,j)$ 的消失影响。 综上，得证。也就是说，对于任何一个最短路上的 $(i,j)$ 一定存在一条边 $(u,v)$ 满足强制走过 $(u,v)$ 的某一条最短路就是删去 $(i,j)$ 的最短路，那个做法就是对的了。 ## 有向图错在了哪里 ``` 5 7 1 3 114514 3 5 114514 1 2 1 3 2 1 2 4 1 4 3 1 4 5 1 ``` graph_editor，请。这个图如果要删掉 $(2,4)$ 这条边，就必须同时强制 $(1,3),(3,5)$ 全部选择才行，任意强制走一条边的最短路都会经过$(2,4)$ 那么证明错在了哪里？我们看那个证明 $a+b<c,a+c<b$ 的部分，我们发现，这个其实是假设了路径可以翻转，但是，有向图破坏了这个假设，所以就证不出来了。 ## 零权边？ 也可以做，我们需要稍微修改这个过程，我们首先确定任意一条最短路 $1\rightsquigarrow n$ ，然后在构建 $S$ 的时候，尽可能的将一个节点与 $n$ 的 lca 变高。这样我们发现，如果 $2a\leq 0$，这导出 $a=0$，也就是 $b=c$，此时我们发现，这个新的最短路并没有满足lca最短（有相同长度但lca更高的），所以就可以啦。 所以我们需要将边权为 0 缩联通块，来构建这样的 $S,T$，就可以了。 或者换句话说，零权边使得结论弱化为了 对于任何一个最短路上的 $(i,j)$ 一定存在一条边 $(u,v)$ 满足强制走过 $(u,v)$ 的，与 **$1\rightsquigarrow n$ 交集最小** 的最短路就是删去 $(i,j)$ 的最短路，那个做法就是对的了。