耳分解小记

Ear Decomposition

耳：对于无向图 \(G = (V, E)\) 和 \(V\) 的一个子集 \(S\)，定义一个耳为一个顶点序列 \(a_1\sim a_m\)，满足 \(a_2\sim a_{m - 1}\in V - S\) 互不相同且和 \(a_1, a_m\) 不同，且 \(a_i\) 和 \(a_{i + 1}\) 之间均有连边。其中 \(a_1\neq a_m\) 时称为开耳。

耳分解：将图分解为一个子图序列 \(G_0, G_1, \dots, G_t\)，满足 \(G_t = G\)，\(G_0\) 是一个环，\(G_i\setminus G_{i-1}\) 构成一个耳。

有向图的定义类似。

不加证明地给出两条结论：

• 有向图强连通 \(\Leftrightarrow\) 存在有向图耳分解。
• 无向图边双连通 \(\Leftrightarrow\) 存在无向图耳分解。

注意到耳的结构是较为简单的，这给我们做题时带来了拆解结构这一不同角度。

GP of Korea, C. Economic One-way Roads

倒做耳分解的过程，从 1 开始一个耳一个耳地加入，设 \(f(S)\) 表示目前点集为 \(S\) 的内部定向边权最小值。转移的时候枚举 \(T(T\cap S = \varnothing)\)，预处理 \(T\) 作为一个耳的最小代价，时间复杂度 \(\mathcal O(3^n n^2)\)。不好过ww。

考虑另一种 dp 方法，从耳的构造过程出发。设 \(dp(S, u, v)\) 表示当前点集为 \(S\)，目前的耳构造到点 \(u\)，终点是点 \(v\) 的最小代价。转移的时候枚举中转点 \(w\notin S\)，计算贡献即可。

比较难受的是，由于是边的定向，\((w, v)\) 和 \((v, w)\) 不能同时出现，所以还要记录一下当前是不是刚从 \(v\to w\) 走出去这样。时间复杂度 \(\mathcal O(2^n n^3)\)。代码上的细节是，一开始要先把所有边定向，后续有需要再反过来。

P5776

基本一样，就是把条件从有向图强连通换成了无向图边双联通。

类似地做一个 dp 即可。状态设计都是一样地。没有写代码，看了看 ix35 聚聚的题解代码，不同的一个细节是 \((u,v)\) 之间有重边的话要保留前 2 小的边，原因显然。