题解 P4208 【[JSOI2008]最小生成树计数】

考虑性质【具有相同权值的边不会超过 $10$ 条】 从一般套路来看，$10$ 可能涉及指数级算法。 |$n^n≈$|$n!≈$|$2^n≈$| |:-:|:-:|:-:| |$1\times10^{10}$|$3.63\times10^6$|$1.02\times 10^3$| ~~所以我们用猜复杂度的方法知道了实际复杂度与 $O(2^n)$ 有关~~ 考虑 $O(2^n)$ 一般的做法：按位枚举。 于是就可以口胡出一种做法，**证明在后** > 做法： > 「一」对于 **``mst`` 上有的边** 的权值（设权值为 $k$，且这样的边在 **原图** 上有 $c$ 条），先连接 **``mst``** 上 **权值非 $k$** 的边（尤指**并查集合并**操作） > 「二」对于剩下的 **原图上的权值为 $k$** 的边，**枚举子集**（即：二进制从 $0$ 到 $2^c$ 枚举） > 「三」对于枚举得到的一种子集，**首先要保证**若这些子集中的边全部加入，得到的图的边数为 $n-1$。 >> 形式化的说，我们要保证 **``mst`` 上权值非 $k$ 的边的条数 + $sizeof\{subset\}(subset \subset E_{edge.val==k}) = n-1$** > 「四」接下来我们要保证若这些子集中的边全部加入，得到的是一棵**树**（而不是非连通图）。这是，我们可以通过类似 ``kruskal`` 的方式利用**并查集**维护点联通关系。只要有任意一条边在连接时导致了环的形成（即：这条边的两个端点早已联通）则这种子集不构成对答案的贡献 >> 注意，由于并查集的**断边**操作十分困难，而且若实现将只能**按秩合并**而不能**路径压缩**，所以我们在枚举子集之前**对 ``fa`` 数组进行备份**，这样可以快速地将 ``fa`` 数组还原到**对这种子集检验之前的情况** 证明：关键点在于证明“在所有最小生成树中，权值相等的边出现的次数相等” 现在我们考虑一颗 ``mst`` 中的两条边 $e_1,e_2$。$e_1$ 连接 $u_1,v_1$，权值为 $w_1$；$e_2$ 连接 $u_2,v_2$，权值为 $w_2$。根据 ``mst`` 性质易知 $u_1,v_1,u_2,v_2$ 中必定有两点可以不经过 $e_1,e_2$ 到达，不妨设为 $v_1,u_2$  **前提** $e_1,e_2$ 与图上**三个蓝框代表的点集合**构成一颗 ``mst`` **假设 1** 有两条不属于 ``mst`` 的边 $e_3,e_4$ 满足其权值均不等于 $e_1,e_2$ 的权值 **假设 2** $e_3,e_4$ 与图上**三个蓝框代表的点集合**能构成一颗 ``mst`` 不妨设 $val_{e_1}<val_{e_2}$ 和 $val_{e_3}<val_{e_4}$。 1. 如果有 $val_{e_3}<val_{e_1}$ ，可知在 ``kruskal`` 中 $e_3$ 先于 $e_1$ 访问。而 $e_3$ 既然能满足**假设 2**，则 $e_3$ 一定会被加入到 ``mst`` 中，与**假设 1**矛盾 2. 如果有 $val_{e_1}<val_{e_3}$，由 **前提** 与 **假设 2** 可知 $val_{e_1}+val_{e_2}=val_{e_3}+val_{e_4}$，所以易得 $val_{e_1}<val_{e_3}<val_{e_4}<val_{e_2}$。此时在 ``kruskal`` 中 $e_3,e_4$ 先于 $e_2$ 访问。而 $e_3,e_4$ 既然能满足**假设 2**，则 $e_3$ 或 $e_4$ 一定会被加入到 ``mst`` 中（且 $e_2$ 将不会被加入到 ``mst`` 中），则可以得出一颗 ``mst`` ，其权值小于原 ``mst``，矛盾。 现在已经可以得出这题的全部解法。 时间复杂度（$D$ 为“具有相同权值的边”的最多个数）： - 枚举所有 **``mst`` 上有的边** 的权值： $\Theta(n)$ - 对于 **原图上的权值为 $k$** 的边 **枚举子集** ：$\Theta(2^{D})$ - 检验方案正确性 ：$\Theta(D)$ 总时间复杂度：$\Theta(nD2^D)$ 代码：[见我的 gitee 仓库](https://gitee.com/hkxa/mycode/blob/master/luogu/P4208.cpp)