POJ1737 题解

__vector__ · 2022-06-01 22:10:30 · 个人记录

前言：

主要是记录一下 \text{\color{black}{皎}\color{red}{月半洒花}} 大佬的讲题思路

题目翻译：

给定一个 n，求由 n 个点组成的无向连通图个数。
多测

正文：

用 h_n 代表 n 个点组成的无向图个数，f_n 代表 n 个点组成的无向连通图个数，g_n 代表 n 个点组成的无向不连通图个数。
来想一下每一项的计算方式：

• h_n
• g_n

  显然，g_n = h_n - f_n

• f_n

  可以将图分割成，「包含 1 的连通块」和「其他点」两个集合。然后枚举 「包含 1 的连通块」 集合的大小从 1 \rightarrow n-1。集合大小为 i ，可以看作在 n-1 个点中挑选 i-1 个非 1 的点，也就是 C_{n-1}^{i-1}。同时这 i 个点还会以 f_i 种形态组成连通图。另外 n-i 个没有选上的点将以 h_{n-i} 种形态组成图。最后答案就是 \sum_1^{n-1} C_{n-1}^{i-1} \cdot f_i \cdot h_{n-i}

现在知道了转移方法，就可以做了。