题解：P15890 [COCI 2025/2026 #6] 抄写 / Prepisivanje

Aron_2023 · 2026-07-22 16:31:04 · 题解

分析

本题就是求二分图中的最大独立集。

把网格中的 0 按照 (i+j) \mod 2 的奇偶性染色，即进行交替染色，形成两个颜色集合。题目度约束条件是 2 位置旁边的 0 不能坐，标记。将能坐的 0 位置互相连边，则网格形成一个二分图，跑匈牙利算法可以得到最大匹配。

根据柯尼希定理，二分图的最小覆盖集等于最大匹配。

::::info[最小覆盖集] 点可以控制其发出的边。选择最少的点，可以控制所有的边，称选择的点最少的集合为最小覆盖集。 ::::

::::info[证明] 记 \tau(G) 为最小点覆盖大小，\nu(G) 为最大匹配边数。

• \tau(G)\le\nu(G)

  取最大匹配 M。走交替路（即从左部未匹配点出发，依次走非匹配边、匹配边、非匹配边……）令 Z 为这样走所有可达的点，L_Z=Z\cap L，R_Z=Z\cap R。构造点集 K=(L\setminus L_Z)\cup R_Z

于是存在大小为 \nu(G) 的点覆盖，\tau(G)\le\nu(G)。综上 \tau(G)=\nu(G)。 ::::

又有最大独立集大小 = 总顶点数 - 最大匹配边数。

::::info[证明] 先证 I 是独立集 \iff V \setminus I 是点覆盖。

• 若 I 独立，则任意边 (u,v) 的两端点不能全在 I 中，故至少有一端在 V \setminus I 里，即 V \setminus I 覆盖所有边。

• 若 K = V \setminus I 是点覆盖，则 I 中任意两点不能相邻（否则该边的两端都不在 K 中），故 I 独立。

于是对任意独立集 I 和点覆盖 K = V \setminus I，有 |I| = |V| - |K|。

取 I 为最大独立集，则 K 为某个点覆盖，故 |K| \ge \tau(G)，从而 |I| \le |V| - \tau(G)。

取 K 为最小点覆盖，则 I = V \setminus K 是独立集，故 |I| \ge |V| - \tau(G)。

因此得证。 ::::