P6596 How Many of Them 做题记录

在无向连通图中，若一条边被删除后，图会分成不连通的两部分，则称该边为割边。

求满足如下条件的无向连通图的数量：

1. 由 $n$ 个结点构成，结点有标号。
2. 割边不超过 $m$ 条。
3. 没有重边和自环。

答案对 $10^{9}+7$ 取模。

$2≤n≤50,0≤m≤\dfrac{n(n-1)}{2}$

设 $dp_{n,m}$ 表示 $n$ 个点，$m$ 条割边的连通有标号无向图的数量，那么可以考虑枚举 $n$ 所在的强连通分量来转移。

发现直接转移不好转，所以加一个辅助数组 $pd_{n,m,k}$ 表示 $n$ 个点，$m$ 条割边，$k$ 个连通块的有标号无向图的数量，那么 $dp_{n,m}$ 的转移就可以枚举 $n$ 所在的强连通分量，然后和其它的连通块都连一条边。显然和其它连通块的每条连边都可以贡献一条割边。

那么有转移：

$dp_{n,m}=\sum\limits_{i=1}^{n-1}\dbinom{n-1}{i-1}dp_{i,0}\sum\limits_{j=1}^{\min(n-i,m)}pd_{n-i,m-j,j}\times i^j$

最后那个 $i^j$ 表示从 $n$ 所在的强连通分量连向 $j$ 个连通块的方案数，注意在这里我们把这 $j$ 个连通块的大小当成了 $1$。

接下来考虑 $pd_{n,m,k}$ 的转移，可以枚举 $n$ 所在的连通块，然后枚举这个连通块里的割边数量：

$pd_{n,m,k}=\sum\limits_{i=1}^n\sum\limits_{j=0}^m\dbinom{n-1}{i-1}dp_{i,j}\times pd_{n-i,m-j,k-1}\times i$

最后的 $\times i$ 是因为之前在转移 $dp$ 时我们把连通块大小当成了 $1$。

不过还有个问题，$dp_{n,0}$ 无法转移，所以需要计算出所有有标号无向连通图的数量再减去有割边的有标号无向连通图的数量，即设 $cnt_u$ 为有标号无向连通图的数量，那么 $dp_{n,0}=cnt_u-\sum\limits_{i=1}^{n-1}dp_{u,i}$。