题解

思路

图论刻画

无向连通图是 2-边连通图，当且仅当图中没有桥。

任意无桥连通图都可以从一个顶点开始，通过不断加入“耳”得到：

• 一条耳是一条简单路径；
• 路径的两个端点已经在当前图中，两个端点可以相同；
• 路径的所有内部点此前都没有出现。

端点相同时，加入的是一条只与旧图共享一个顶点的环。这个情形必须保留，否则无法表示多个环共用割点的图。

若一条耳有 $s$ 个内部点，它恰好加入 $s+1$ 条边。因此，问题转化为：把所有顶点分批作为耳的内部点加入，并最小化各耳的边数之和。

做法

子任务 1：枚举保留边集

当 $n\le6$ 时，最多只有 $15$ 条边。按照保留边数从小到大枚举边集，对每个候选子图运行一次 Tarjan 桥检测。第一个连通且无桥的候选就是最优答案。

复杂度为 $O(2^m(n+m))$。

子任务 2：显式枚举简单耳

当 $n\le9$ 时，从每个起点执行 DFS，显式枚举所有不重复顶点的简单路径与简单环。对每个内部点集合 $S$，记录一条端点为 $x,y$ 的耳。

令 $f[T]$ 表示已经覆盖顶点集合 $T$ 时的最少边数，固定顶点 $1$ 最先被覆盖。若存在一条内部点集合为 $S$、两个端点都在 $T\setminus S$ 中的耳，则

显式枚举简单路径是阶乘级的，但在 $n\le9$ 时可行。它把边集搜索升级为耳分解状态，但还没有解决简单路径枚举的瓶颈。

满分算法：端点—内部点集路径 DP

定义布尔状态

表示存在一条从 $x$ 到 $y$ 的简单路径，其内部点集合恰好为 $S$，且 $x,y\notin S$。允许 $x=y$，此时状态表示一条简单环。

对输入中的每条边 $(x,y)$，初始化 $P_{x,y,\varnothing}=1$。若 $P_{x,y,S}=1$，并且 $z$ 尚未出现在路径中且 $(y,z)$ 是输入边，则可以转移到

需要排除在 $S=\varnothing$ 时沿同一条边立刻返回起点的伪二元环。

得到全部耳状态后，仍使用上一节的集合 DP。实现中为每个内部集合 $S$ 建立端点要求的向上闭包：只要已覆盖集合包含某一对合法端点，就可以在 $O(1)$ 时间判断该耳能否附着。所有互不相交的“已覆盖集合—新内部集合”组合总数为 $3^n$。

时间复杂度为 $O(n^3 2^n+n3^n)$，空间复杂度为 $O(n^2 2^n+3^n)$。

方案恢复

集合 DP 为每个状态记录最后加入的内部点集合以及耳的两个端点。路径 DP 同时记录每个状态最后一步的前驱。逆序回溯集合 DP，再沿路径前驱逐条输出道路，即可得到最优保留边集。

正确性证明

首先，每次加入的耳只有端点属于旧图，内部点全新。耳上的每条新边都位于由该耳与旧图中端点间路径组成的环上；端点相同的闭耳本身就是一个环。因此，从第一条闭耳开始，逐次加耳后所得图始终连通且无桥。

其次，任意无桥连通图都存在允许闭耳的耳分解。取任意一个顶点作为初始覆盖集合，依次考察耳分解中的耳，它们恰好对应集合 DP 的一系列合法转移，且每条耳贡献“内部点数加一”条边。因此，集合 DP 不会遗漏任何可行最优子图。

综上，DP 得到的值既能构造出一个无桥连通子图，又不大于任意可行子图的边数，所以输出方案最优。

复杂度

• 子任务 1 的时间复杂度为 $O(2^m(n+m))$，空间复杂度为 $O(n+m)$。
• 子任务 2 的显式路径枚举为阶乘级，集合合并部分为 $O(n^2 3^n)$，空间复杂度为 $O(n^2 2^n)$。
• 满分算法的时间复杂度为 $O(n^3 2^n+n3^n)$，空间复杂度为 $O(n^2 2^n+3^n)$。

评测说明

本题允许多种最优方案。Testlib 评测器会验证：

1. 输出道路均属于原图且互不重复；
2. 保留图覆盖全部顶点、连通且没有桥；
3. 输出道路数等于标准答案中的最优道路数；
4. 输出结束后没有多余内容。