题解：P5776 [SNOI2013] Quare

Lovya · 2026-03-08 23:32:45 · 题解

:::info[简要题意]{open}

给定一个 n 个点，m 条边的带权无向图，寻找一个边双连通子图，使其边权和最小。可能有重边。

::::

:::info[耳与耳分解的定义]{open}

假如图 G 有一个真子图 G^{\prime}，点 a 为 G^{\prime} 上一点。点 a 与 G^{\prime} 外一点相连。假如此点有另一条不经过点 a 的路径连到 G^{\prime}，设这条路径连到 G^{\prime} 内的点 b。称点 a 到点 b 的 G^{\prime} 外路径为耳。若一个图 G 可以拆为一个环（即简单回路）与多个耳，则称图 G 可以耳分解。

:::

::::info[结论：图 G 边双连通 \Lrarr 图 G 存在耳分解]{open}

:::info[必要性证明：若图 G 存在耳分解，则图 G 边双连通]{open}

由于图 G 存在耳分解，则图 G 必含环。任取一环作为 G_0。当 G_0=G 时，证明完成。否则，设已证得 G 的真子图 G_{i-1} 边双连通，考虑 G_i = G_{i-1} \cup P_i，其中 P_i 是一个耳，P_i 的两端点为 a,b。下证 G_i 边双连通。

由于 G_{i-1} 连通，且点 a,b 在 G_{i-1} 中，故 G_i 连通。

反证：假设 G_i 有割边 e=(u,v)。

分类讨论：

删去 e 后，有路径 u\to a\to b\to v，得到一条连接 u 与 v 的路径，故 e 非割边。

显然，因 G_{i-1} 边双连通，因此， G_{i-1} 中无割边。故，e 非割边。

上述两种情况均矛盾，故 G_i 无割边，即 G_i 边双连通。归纳可得，G_k = G 边双连通。

:::

:::info[充分性证明：若图 G 边双连通，则图 G 存在耳分解]{open}

由于图 G 边双连通，图 G 必含环。任取一环作为 G_0。当 G_0=G 时，分解完成。否则，设已构造出 G 的真子图 G_i，且 G_i 满足可由 G_0 逐步添加耳得到。

由于 G_i 为 G 的真子图，故有 G_i\not=G。因此，必存在一条边 (u,v)，满足 u \in G_i,v \not \in G_i。根据边双连通的定义，删去边 (u,v) 后必存在另一条路径使得 v 与 G_i 连通。取删去边 (u,v) 后的图 G 中 v 到 G_i 的最短路径为 P，设其终点为 w。令 P'=(u,v)\cup P，则 P' 为 G_i 的一个耳。将 P' 加入 G_i 得 G_{i+1}=G_i\cup P'。重复此过程，每次至少增加一条新边，有限步后得 G，即得耳分解。

:::

::::