传送门

交通运输（Wormhole Transportaion）

题目大意

有 \(n\) 个点和 \(m\) 个点对，你需要构造一张 \(m-1\) 条边的无向图，使得 \(m\) 个点对间最短路之和最小。

求最小值及取到最小值的方案数。

\(2 \le n \le 2000,2 \le nm \le 2 \times 10^7,1 \le u_i,v_i \le n,u_i \neq v_i\)。

保证所有无序对 \((u_i,v_i)\) 两两不同，且至少存在一种合法的方案。

仙人掌森林：每条边在至多一个简单环中的无向图。

杏仁：恰好存在两个度数大于 \(2\) 的结点，其他结点度数都等于 \(2\)，且所有环都经过两个度数大于 \(2\) 的结点的连通无向图。

思路

称以 \((u_i,v_i)\) 为无向边的图为 \(G\)，我们构造的图为 \(G'\)。

定义 “删去” 表示这条边或路径在 \(G\) 中，但不在 \(G'\) 中。“保留” 表示这条边或路径既在 \(G\) 中也在 \(G'\) 中。

令 \(d(u,v)\) 表示在 \(G'\) 中 \(u\) 到 \(v\) 的最短路。

求解最短路最小值

题目中保证至少存在一种合法的方案，那么我们可以知道，\(G\) 中一定有环。

若 \(G\) 中无环，那么 \(G\) 就是普通森林，对于任意森林里的一棵树 \(T\)，令其有 \(k\) 条边，\(k+1\) 个节点。

由于 \(T\) 有 \(k+1\) 个节点，所以我们要使其连通至少需要 \(k\) 条边。那么我们所需的总边数为 \(m\)，大于题目要求的 \(m-1\)，所以不存在合法方案，矛盾。

那么我们就可以猜测，最短路最小值与环有关。

设环内边数量为 \(x\)。

先考虑环外的边。

我们观察不在 \(G\) 的环上的边 \((5,6)\)。

假设我们选择了一个中转点进行连边。

可以发现，如果我们选择一个不在 \(G\) 中的中转点 \(7\)，那么我们会连接 \((5,7),(6,7)\) 两条边，\(d(5,6)=2\)，使用两条边。但实际上我们可以连接 \((5,6)\)，此时 \(d(5,6)=1\) 且只使用了一条边。

所以，我们不会选择不在 \(G\) 中的节点作中转。

同样的，如果我们选择一个在 \(G\) 中的中转点 \(2\)，那么我们会连接 \((2,5),(2,6)\) 两条边，\(d(5,6)+d(2,6)=3\)，使用两条边。但如果我们连接 \((5,6),(2,6)\)，\(d(5,6)+d(2,6)=2\)，同样使用两条边。

所以，我们不会选择在 \(G\) 中的节点作中转。

综上，我们不会作中转。

也就是说，如果 \((u,v) \in G\)，且 \((u,v)\) 不是环边，那么 \((u,v) \in G'\)。

根据这条性质，我们可以知道，环外的边的答案就是 \(m-x\)。

接下来考虑环内的边。

我们假设这个环长度为 \(k\)。

显然，如图所示将环断成一条链最优。答案为 \(2 \times (k - 1)\)。

那如果有多个环？显然我们只需断一个环。而又因为我们要让答案最小，即选择一个环 \(i\) 使 \(2 \times (k_i - 1)\) 最小，所以 \(i\) 一定是最小环。

我们设最小环的长度为 \(cnt\)，那么最后的答案就是 \(x-1+cnt-1=x+cnt-2\)。

这样我们就算出了总答案为 \((m-x)+(x+cnt-2)=m-cnt-2\)。

sub2

\(G\) 是一个大小为 \(n\)，编号顺次为 \(1,2,3,\dots,n\)​ 的环。

此时 \(G'\) 是一棵树，我们令 \(G'\) 的根节点为 \(1\)。

我们只需要计算使 \(d(1,2)+d(2,3)+\cdots+d(n-1,n)+d(n,1)=2n-2\) 成立的 \(G'\) 的个数。

可以发现，\(d\) 的和实际上就是 \(1 \to 2 \to \dots \to n \to 1\) 的路径长，而 \(2n-2\) 代表每条边正好经过两次。如上图红色路径所示。

那么这样的路径实际上就是我们 dfs 的遍历过程，也就是说 \(1,2,\dots,n\) 是 \(G'\) 的欧拉序的子序列。

所以任意一个子树内所有节点的编号必定构成连续区间。下方称此结论为条件 \(1\)。

然后考虑如何计数。

我们设在 \(G'\) 中，\(1\) 的儿子中编号最大的是 \(y\)，子树 \(y\) 中点的编号是 \([x,n]\)。

不难发现，除去子树 \(y\) 后的树编号是 \([1,x-1]\)，也满足条件 \(1\)，是一个子问题。

但因为 \(y\) 不是 \([x,n]\) 中编号最大的点，所以它不是子问题。但是如果我们将它拆分成 \([x,y]\) 和 \([y,n]\) 两个区间，我们发现，这两个区间都是满足条件 \(1\) 的，都是子问题。

那么我们就把答案拆分成了三个子问题：\([1,x-1],[x,y],[y,n]\)。

\([1,x-1]\) 而不是 \([1,x]\) 是因为 \(y\) 是 \(1\) 的儿子，\((1,y)\) 这条边一定存在。

发现区间的左右端点对答案没有影响，所以设 \(f_i\) 表示长度为 \(i\) 的连续区间的方案数。

那么答案 \(f_n=\sum_{i+j+k=n+1} f_i f_j f_k\)。用 \(h_n=\sum_{i+j=n} f_i f_j\) 辅助计算就可以达到 \(O(n^2)\)。

sub3

\(G\) 是仙人掌森林。

那么我们只需要找出最小环的个数 \(tot\)，然后将最小环的答案乘上 \(tot\) 就好了。

注意不是乘方，时刻牢记我们只断一个环。

sub4

\(G\) 是杏仁。

题目中说，杏仁是恰好存在两个度数大于 \(2\) 的结点，其他结点度数都等于 \(2\)，且所有环都经过两个度数大于 \(2\) 的结点的连通无向图。

我们翻译一下：\(G\) 中有两个点 \(S,T\)，它们之间有 \(k\) 条不交路径，如下图。我们设这些路径长度从小到大依次为 \(L_1,L_2,\dots,L_k\)。

显然最小环的长度 \(cnt=L_1+L_2\)，数量 \(tot\) 也好算，但是我们不能用 \(f_{cnt}\) 乘以数量来计算答案，因为会算重。

思考什么时候会算重。

如图，我们令绿色的环为 \(x\)，红色的环为 \(y\)，路径 \(S \to 3 \to T\) 为 \(L_1\)，\(S \to 1 \to 2 \to T\) 为 \(L_2\)，\(S \to 4 \to 5 \to T\) 为 \(L_3\)。

发现保留路径 \(L_2\)，改变 \(L_1\) 与保留路径 \(L_3\)，改变 \(L_1\) 的方案是完全重复的。

据此，我们定义 \(g_{a,b}\) 表示长度为 \(a\) 和 \(b\) 的路径构成的最小环中，保留路径 \(b\) 的方案数。那么对于上图情况，最后答案就是 \(2f_5-g_{2,3}\)。

拓展到整个图，令长为 \(L_1\) 的路径个数为 \(t_1\)，长为 \(L_2\) 的路径个数为 \(t_2\)：

• 当 \(t_1 \neq 1\) 时，答案为 \(tot \times f_{cnt} - t_1 \times (t_1-1) \times g_{L_1,L_1}\)。
• 当 \(t_1 = 1\) 时，答案为 \(tot \times f_{cnt} - t_2 \times (g_{L_1,L_2}+g_{L_2,L_1})\)。

现在只需要考虑怎么计算 \(g_{a,b}\) 了。

可以发现与条件 \(1\) 差别不大，可以推出 \(g_{a,b}=\sum_{i+j=a+1} f_i f_j\)。

发现其实与 \(b\) 无关，所以直接定义 \(g_i\) 为只更改最小环上长度为 \(i\) 的路径的方案数。

sub6

没有特殊限制。

我们类比 sub4 的解法，定义一个 \(G'\) 被图 \(G\) 中的环 \(C\) 影响，当且仅当所有不在 \(C\) 上的 \((u,v) \in G'\)。

如果 \(G'\) 被 \(C_1,C_2,\dots,C_t\) 影响，那么 \(G'\) 只能在 \(G\) 中 \(C_1,C_2,\dots,C_t\) 相交的路径 \(P\) 上作修改得到。

那么对于求解方案，我们可以找到 \(P\) 上的一段区间 \(P'\)，长度为 \(P'_l\)，然后只对 \(P'\) 进行改动。

发现这与我们 \(g\) 数组的定义很像。但是要注意的是，这里 \(P'\) 的端点所连的边也都会改动，所以我们要做一个容斥，答案是 \(g_{P'_l}+g_{P'_l-2}-2 \times g_{P'_l-1}\)。

但是其实可以发现，对于 \(G'\) 只被一个环 \(C\) 影响时，我们无法完全计算到它的贡献。因为多个环的相交部分一定不大于 \(\frac{cnt}{2}\)。

设 \(L\) 为组成最小环的路径，其中 \(L_1,L_2\) 与 \(L_1,L_3\) 均构成最小环。

如果相交部分 \(L_1 > \frac{cnt}{2}\)，那么 \(L_1>\frac{L_1+L_2}{2}\)，即 \(L_1>L_2\)，同理 \(L_1>L_3\)。

此时发现 \(L_2+L_3<L_1+L_2\)，即 \(L_2+L_3<cnt\)，与 \(cnt\) 为最小环长的定义矛盾。

那么我们就需要统计 \(G'\) 只被一个环 \(C\) 影响的部分答案。

那么我们只需要进行一个容斥即可。

我们令在 \(G\) 中 \(dis(i,j)\) 表示 \(i\) 到 \(j\) 的最短路。

那么首先我们需要找出最小环长度 \(cnt\) 和数量 \(tot\)，然后将 \(f\) 数组和 \(g\) 数组计算出来。

接下来我们枚举每个路径 \(P'\)，即枚举路径的端点 \(s,t\)，注意需要保证 \(dis(s,t) \le \frac{cnt}{2}\)。对答案的贡献为 \(g_{dis(s,t)}+g_{dis(s,t)-2}-2 \times g_{dis(s,t)-1}\)。

最后用容斥统计 \(G'\) 只被一个环 \(C\) 影响的部分答案。

然后将单个最小环的答案乘上 \(tot\)​，按 sub4 的方法去重就好了。

分析时间复杂度。

处理两点之间最短路、两点之间第一条路与最短路不同的最短路和最小环信息，用 bfs 可以做到 \(O(nm)\)。

\(f\) 数组与 \(g\) 数组。直接处理是 \(O(n^3)\)，按 sub2 所述优化是 \(O(n^2)\)。

枚举路径计算答案是 \(O(n^2)\)。

总时间复杂度 \(O(nm+n^2)\)。

那么终于，这道题结束了。

代码实现

太难写了，先咕一会。

尾声

如果你发现了问题，你可以直接回复这篇题解

如果你有更好的想法，也可以直接回复！