专题题解 - 交通运输

发表于 分类于
Luogu P7729

前言

本题是洛谷 2021 年 7 月月赛的 F 题，出题人是 zjc，验题人是我。

当时由于我的月赛已经有了五题，然后碰巧 zjc 又投了一题，就正好凑了一场月赛。本题难度很高，场上最高分和次高分分别是 jiangly 的 86 分和铃的 53 分。

在比赛结束后的一年之内都没有人 AC 这道题目，直到上个月，我在好题分享时分享了此题，才有一位实力非常强劲的同学通过本题。于是我想公开一下此题的题解，以期让更多人做到这道好题。

Part 0：题意

题目大意：有 $n$ 个点，给定 $m$ 个点对，现在需要构造一张 $m-1$ 条边的无向图，使得 $m$ 个点对之间的最短路之和最小。求最小值和取到最小值的连边方案数。

$n\leq 2000, n\times m\leq 2\times 10^7$

Part 1：第一问

本题的一个首要的观察是要知道第一问的答案。

引理 1. 设 $m$ 个点对构成的无向图为 $G$，求 $G$ 中的最小环长度 $l$，则第一问的答案为 $m+l-2$。

同时我们可以得到关于连边方案的推论：

推论 1. 一个连边方案是合法的（即可以最小化最短路之和），当且仅当存在一个 $G$ 的最小圈，使得 $G$ 的不在最小环上的边都连了，而且该最小圈上的 $l$ 个点之间连了一棵树，使得环上相邻点的最短路之和恰好为 $2l-2$。

由于证明和题目做法没有太大关联，所以请参考出题人的回答：https://www.zhihu.com/question/469848445/answer/1998538740 。

最小圈的长度是很容易计算的，接下来我们探讨的就是如何求第二问的答案。

Part 2：环

当 $G$ 本身是环时，最小环长度就是 $n$，根据推论 1，我们只需要计算：有多少种 $n$ 个点的树 $T$，使得 $dis(1,2)+dis(2,3)+\ldots+dis(n-1,n)+dis(n,1)=2n-2$。

我们将树看作以 $n$ 为根的，那么有结论：

引理 2. 树 $T$ 符合条件，当且仅当以每个点 $i$ 为根的子树中，点的标号构成一个连续区间。

证明：考虑 $2n-2$ 这个距离之和，一定是每条边在 $1\to 2\to\ldots n\to 1$ 这个过程中恰好经过两次，所以一个点子树内和子树外分别是环上一段连续区间，由于 $n$ 在子树外（$i=n$ 的情况是平凡的），所以子树内就必然是一段区间了。上述过程同时证明了充分性和必要性。

考虑如何计数，设 $n$ 的编号最小的儿子为 $b_1$，$b_1$ 子树内点的标号为 $[1,c_1]$。

那么 $[c_1+1,n]$ 中的点也构成了一棵符合引理 2 条件的树。再考虑以 $b_1$ 为根的子树，由于 $b_1$ 并不是标号最大的点，所以不能直接递归，但我们可以拆分为 $[1,b_1]$ 和 $[b_1,c_1]$ 两部分，不难发现这两部分也都是符合引理 2 条件的树（其中对于后者，$b_1$ 是编号最小的点，和编号最大显然是等价的），所以我们可以将 $[1,n]$ 唯一分解成 $[1,b_1],[b_1,c_1],[c_1+1,n]$ 三段，每段都是一个子问题。

于是设 $f_n$ 表示答案，就有 $f_n=\sum_{a+b+c=n+1}f_af_bf_c$。

Part 2.5：仙人掌

仙人掌的每个环可以看作是独立的，因此假设有 $c$ 个最小环，算出最小环对应的答案 $f_l$ 后乘上 $c$ 即可。

Part 3：杏仁

杏仁指的是这样的图：由两个点 $s,t$ 和它们之间的 $k$ 条不交路径组成，设这些路径的长度分别为 $L_1\leq \ldots\leq L_k$。

我认为设计杏仁的部分分是这题设计上很精彩的一处。对正解有不错的启发作用。

最小环长度一定是 $L_1+L_2$，最小环个数也并不难算，但现在我们面临的问题是：不能直接把最小环个数和 $f_l$ 相乘直接得到答案，因为可能算重。

例如 $L_1+L_2$ 和 $L_1+L_3$ 是两个不同的最小环，但是如果一种连边方案包含了 $L_2,L_3,\ldots,L_k$ 中的所有边，只改变了 $L_1$ 中点之间的连边，那么就会被在两个环里各算一次，产生重复。

为此我们需要容斥。设 $h(a,b)$ 表示在两条长度分别为 $a,b$ 的首尾相接的路径 $A,B$（构成一个长度 $a+b$ 的环）上构造满足引理 2 的树，并且 $B$ 中除了起点终点外的点连边均不变（也就是保留 $B$ 中所有边，且 $A,B$ 独有的点之间没有边）的方案数。

对于上面算重的问题，我们只需减掉 $h(L_1,L_2)$ 对应的这些情况即可得到正确答案。

如何计算 $h(a,b)$ 呢？我们有如下结论：

引理 3. 一个树符合 $h(a,b)$ 的要求，当且仅当它符合引理 2 的要求，并且排除 $B$ 中的边后，$A$ 中的点形成的两个连通块分别是 $A$ 的一段前缀和一段后缀。

证明：根据引理 2 的证明我们知道，删除一条边后树的每个连通块都是环上连续段，于是我们删去 $B$ 中任意一条边，构成的两个连通块都是环上连续段，那么一定分别包含 $A$ 的一段前缀和后缀。

所以我们枚举前缀的长度就可以了，即 $h(a,b)=h(a)=\sum_{c+d=a+1}f_cf_d$，和 $b$ 无关。

Part 4：一般图

进行和杏仁类似的思考，对于一种连边方案 $G_0$ 和一个最小环 $C$，我们称 $G_0$ 服从 $C$ 当且仅当：

  • 对于 $G$ 的任意不属于 $C$ 的顶点集导出子图的边，它都在 $G_0$ 中出现。

也就是我们可以把一种方案 $G_0$ 关联到若干个最小环，这些最小环可以作为推论 1 中所说的 $G_0$ 对应到的最小环。

我们的想法依旧是分成 $G_0$ 服从的最小环唯一和不唯一这两种情况来讨论：

  • Case 1：$G_0$ 服从的最小环不唯一。

    设 $G_0$ 服从最小环 $C_1,\ldots,C_k$，那么 $G_0$ 只能改动 $G$ 的在 $C_1,\ldots,C_k$ 交集中的边，我们设它们的交集是 $D$。一个结论是：$D$ 必然是一条长度不超过 $\frac{l}{2}$ 的路径（读者自证）。

    更进一步地，我们可以找到路径 $D$ 上的一个区间 $P$，使得 $P$ 的第一条边和最后一条边都不属于 $G_0$（只需把 $D$ 的属于 $G_0$ 的前后缀剥掉即可），这样的 $P$ 是由 $G_0$ 唯一确定的。

    我们枚举 $P$，设其长度为 $p$，我们只能改动这条路径上的边，于是我们回想起上一部分中的结论，答案几乎就是 $h(p)=\sum_{a+b=p+1}f_af_b$，但是我们还需要注意这里加了一个 $P$ 的两端都不属于 $G_0$ 的限制，因此我们容斥一下，就是 $h(p)+h(p-2)-2\times h(p-1)$。

  • Case 2：$G_0$ 服从的最小环唯一。

    其实我们仔细推敲一下就会发现，上一部分并不是只算了 $G_0$ 服从的最小环不唯一的情况，毕竟我们只是要求 $G_0$ 只改动了 $G$ 上一段长度不超过 $\frac{l}{2}$ 的路径上的边这个条件。所以这里我们实际上要统计的是不满足这一条件的 $G_0$ 数量。

    有了上一段的基础，这里就比较简单了，对于一个最小环 $C$，我们要求 $G_0$ 不能包含任何长度不小于一半的区间，由于我们已经会算反面，所以利用上文的 $h(p)$ 做个容斥即可，式子比较类似于二项式反演，这里从略。

Part 5：步骤总结

Step 1：首先求出任意两点间最短路 $dis_{i,j}$，第一条边和最短路不同的最短路 $se_{i,j}$，最短路的数量 $cnt_{i,j}$，同时求出最小环长 $l$ 和最小环个数 $c$（最小环一定是由 $dis_{i,j}+se_{i,j}$ 构成，所以可以方便地统计数量）。这可以对每个起点 BFS 做到 $O(nm)$。

Step 2：计算 $f_n$ 和 $h(n)$。观察递推式 $f_n=\sum_{a+b+c=n+1}f_af_bf_c$，利用辅助数组 $g_n=\sum_{a+b=n}f_af_b$ 就可以做到 $O(n^2)$，当然也可以求出封闭形式后 $O(n)$ 解决，但没有必要；而 $h(n)$ 直接算就是 $O(n^2)$ 的。

Step 3：枚举 $P$ 并统计 Case 1 的答案。我们只需枚举 $P$ 的端点 $s,t$ 即可，要求 $dis_{s,t}\leq \frac{l}{2}$，这种情况每个 $P$ 的答案都是 $h(dis)+h(dis-2)-2\times h(dis-1)$，枚举的时间复杂度为 $O(n^2)$。

Step 4：统计 Case 2 的答案。进行容斥后将单个最小环的答案乘上 $c$ 即可，时间复杂度为 $O(n^2)$。

于是最终时间复杂度为 $O(n(n+m))$。