P7729 交通运输 题解

ix35 · 2022-08-18 23:14:42 · 题解

前言

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

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

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

Part 0：题意

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

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))。