专题题解 - Quare

发表于 分类于
Luogu P5776

作为一道求包含所有点的最小权边双连通子图的状压 DP 题，做法与其强连通分量版本 https://codeforces.ml/gym/102759/problem/C 是近乎一样的。

首先我们需要了解 耳分解。

这里这样定义耳（不知道是否标准）：对于（强）连通图 $G$，耳是一条路径 $a_1\to \ldots\to a_m$，满足 $a_1,\ldots,a_{m-1}$ 两两不同且 $a_2,\ldots,a_m$ 两两不同（也就是说是一条简单路径或简单圈），并且 $a_2,\ldots,a_{m-1}$ 的度数都为 $2$，并且删除这上面所有边后不影响 $a_2,\ldots,a_{m-1}$ 以外点的（强）连通性。

定义一张图是可耳分解的，当且仅当可以每次从中删去一个耳，并且最终所有边都被删除。

我们有如下定理：

一张有向图是可耳分解的，当且仅当它强连通。

一张无向图是可耳分解的，当且仅当它边双联通。

上一条定理是用来做那道 open cup 题的，而下一条则是做本题的。

于是我们有一个 naive 算法，倒做耳分解，往一个空图中不断加耳。

令 $f(S)$ 表示包含集合 $S$ 中所有点的最小权双连通分量，枚举与 $S$ 不交的点集 $T$，将 $T$ 连成耳后两端与 $S$ 中的某两个点连接即可，时间复杂度为 $O(3^n\times \operatorname{poly}(n))$。

但是 naive 算法还是 naive 算法，就算能过这题也过不了那个有向图版本，我们进行一个优化。

上面将耳看做了一个整体，但我们不妨将耳逐步加入，具体地，令 $f(S,i,j)$ 表示当前考虑了 $S$ 中的点，但是 $S$ 中最后加入的一个耳还是不完整的，耳伸出去部分的一个端点是 $i$，最终需要与 $j$ 连接上，此时已经加入的所有边的最小权值和。

那么转移只要每次枚举耳上 $i$ 的后继即可。

时间复杂度为 $O(2^n\times \operatorname{poly}(n))$，注意实现细节。

目前这份代码是本题最优解。