小马恶魔城：E 最后的斗争

# 题解 for E：最后的斗争
[E.pdf](http://leanote.com/api/file/getAttach?fileId=5bb6bc4bab644121d7001378)
带标号**边-双联通**图计数。

先看这道题的部分分：

对于$30\%$ 的数据，我们写一个dfs，找出所有的$N$个点的**边-双联通**图打表即可获得。

仍然是对于$30\%$ 的数据，我们不用dfs打表，查询OEIS即可获得前16项。[使用OEIS](http://oeis.org/A095983)

接下来我们具体讨论两种$100$分的做法：

## 思路1 ： 容斥

我们先来考虑**边-双联通**图的特殊性，发现**边-双联通**图缩点后一定是一棵树。

那么我们不妨考虑弱化版的问题：$N$个点带标号的无根树有多少种。

对于这个问题其实我们可以使用$prufer$序列来做到$O(log n)$解决，同时我们也有一种$O(n^2)$的$dp$。

每次考虑对叶子节点进行容斥，通过加入$i$个叶子节点来使得叶子节点数大于$i$：
$$
f_i=\sum^{n}_{i=1}(-1)^{i+1}\binom n i {(n-i)}^i f_{n-i}
$$
表示枚举在大小为$n-i$的带标号无根树下挂上$i$个选出来的叶子。叶子的数量满足容斥原理。

考虑叶子和原树如何连边，发现相当于每一个叶子可以选择原树的$n-i$个点中的任意一个挂在下面。

那么，同样的思想在**边-双联通**图的计数问题种是否会大放光彩呢？

我们考虑记录$h(n, k)$表示有$n$个点，缩点后有$k$个相互连通的连通块的带标号无向图有多少种。

再考虑记录$g(n, k)$表示有$n$个点，缩点后有$k$个互相分开没有连边的连通块的带标号无向图有多少种。

同样的我们模仿刚才的过程，但是有一个问题，我们如果只算连通块没有枚举所有的答案。

考虑下图的情况

![图片标题](https://leanote.com/api/file/getImage?fileId=5bb62d03ab644147a9004163)

设四个点的连通块为$A$，三个点的为$B$，在枚举的时候我们只考虑了$A\to B$的连边。但实际上内部的连边情况比想象中的要复杂，事实上我们可以从$A,B$中各自任意选择一个点将它们连边，一共的方案有$3\times 4=12$种方案，这怎么办呢？

其实这个问题也很好解决，我们再求一个数组$G(n,k)$是$g$的另一个版本。一个方案在$g$种的贡献是1，而在$G$中的贡献为所有的连通块大小相乘。因为我们发现，其实对于挂在原树上这一步操作来说，枚举连通块是无意义的，我们可以直接用点来选择。也就是说，对于枚举的每一个"大型叶子"，我们仍然是在原树中找一个点把它挂上，这里是不影响的。然后我们现在只是同时要在叶子中每一个连通块选出一个点当作连接原树点的"使者"。这里我们不好算，所以用乘法原理直接维护$G(n,k)$。于是我们就基本做完了这道题。
$$
h(n,k) = \sum_{j,l} (-1)^{j+1}\binom n i G(i,j)(n-i)^jh(n-i,l)
$$
同时，通过枚举标号为$1$的点所在连通块的套路：
$$
G(n,k)=\sum^n_{i=1} i\cdot \binom {n-1} {i-1}G(n-i,k-1)
$$

$$
g(n,k)=\sum^n_{i=1} \binom {n-1} {i-1}g(n-i,k-1)
$$

通过进一步推导，我们就可以在$O(n^4)$之内完成这道题，但是这个方法带了很大常数，不太优雅。

## 思路2：进一步的性质

为什么上面的$dp$会如此不优雅呢？我们没有挖掘**边-双联通**图更特殊的性质。

考虑枚举**边-双联通**图特有的东西：桥。

设$g(n,k)$表示$n$个点，$k$个桥的方案数，那么我们每次枚举一个桥。枚举内容包括桥的两个端点以及桥连通的两个无向连通图。
$$
g(n,k)=(\sum \binom n 2 \binom {n-2} {i-1} g(i,j)g(n-i,k-j-1))/k
$$
表示先选两个点作为桥的两个端点，然后选出两个连通块内的点，接着枚举两个连通块的形态。

考虑对于有$k$个桥的图来说，每一个方案按这样算都会被算$k$次，因为图内的每一个桥都算了一次。

但是这个$dp$有一个问题，我们最终的答案是$g(n,0)$，但是这个式子并不能推出$g(n,0)$，考虑用代标号连通图的个数减去所有的桥不为$0$的图的个数就可以获得$g(n,0)$了。

至此，我们仅仅用两个$dp$完美解决了这道题，复杂度$O(n^4)$。

Rockdu's Blog

导航

最近发表

大佬们的友链