耳分解小记

在有向（强）连通图中，定义“耳”为一条简单路径/一个简单环 \(a_1\to a_2\to\cdots\to a_k\)，使得删去所有这些边之后不影响除了 \(a_2,a_3,\dots,a_{k-1}\) 的点的（强）连通性。

无向图中也有类似定义。

有以下结论：

• 一张有向图可以被耳分解当且仅当其强连通。
• 一张无向图可以被耳分解当且仅当其边双连通。

先看一道题：XXI Open Cup, Grand Prix of Korea C. Economic One-way Roads。

题意即给定一张无向图，要你为它的每条边定向，每条边定为不同的方向有不同的代价，问使得定向之后该图强连通的最小代价。点数 \(2\le n\le 18\)。

首先随便定向，每条边定为代价较小的那一方向（因为每条边都要被定向）。

考虑反着做耳分解，每次尝试找一条简单路径/一个简单环。

设 \(f_S\) 表示 \(S\) 内的点集强连通的最小代价；\(g_{S,i,j}\) 表示目前经过的点集为 \(S\)，当前需要连通 \(i,j\) 两点。

转移的话可以直接枚举 \(i\) 的后继 \(k\)，然后有 \(g_{S\cup\{k\},k,j}\leftarrow \min(g_{S\cup\{k\},k,j}, g_{S,i,j}+a_{i,k})\)。如果 \(k\) 和 \(j\) 有边相连那么可以顺带更新 \(f_{S\cup\{k\}}\)。

代码：https://pastebin.ubuntu.com/p/VkDSDkVzzQ/。

还有无向图版本：[SNOI2013] Quare。

跟上面类似，只需要注意类似 \(x\to y\to x\) 的转移也是合法的，需要在枚举完 \(S,i,j\) 之后再特判一下这种转移。

代码：https://pastebin.ubuntu.com/p/9bmFRX4gHK/。

参考：https://www.cnblogs.com/xiaoziyao/p/16441805.html。