种西瓜 2：题解¶

解法改进：Codex（GPT-6）。 本解法简化枚举集合的可行性判定，并结合已有的格雷码与增广路方法，设计和实现了适用于本题的增量匹配解法，将时间复杂度改进为 \(O(p2^p)\) .

终止状态是极大匹配¶

把瓜藤和地块作为二分图的两部，指定关系作为边。一条实际生长的关系对应一条匹配边。终止意味着没有两端都未匹配的边，因此要求的是边数最少的极大匹配。任意极大匹配都可以依次执行其中各条生长关系得到。

记所有瓜藤为 \(L\) .枚举集合 \(S\subseteq L\) ，允许其中的瓜藤结瓜；不要求它们最终全部结瓜。集合外的瓜藤必须保持未匹配，因此其所有邻居都需要被占用。定义

\[ R=N(L\setminus S) \]

仅需判断二分图 \(G[S,R]\) 中是否存在覆盖整个 \(R\) 的匹配。设其最大匹配大小为 \(\nu(S,R)\) ，判定条件就是

\[ \nu(S,R)=|R| \]

为什么可以用通过判定的最小 \(|S|\) 作为答案？

通过判定时，先执行覆盖 \(R\) 的匹配，再让 \(S\) 内尚未结瓜的瓜藤向其余空地继续生长，直到不能继续。整个过程中 \(R\) 始终被占用，集合外的瓜藤一直没有机会。最终得到一个极大匹配，边数至多为 \(|S|\) .
对一个最优终止方案，取实际结瓜的瓜藤组成 \(S\) .因为集合外瓜藤无法生长，\(R\) 已全部被占用；最优方案中指向 \(R\) 的那些边就构成覆盖 \(R\) 的匹配。该集合通过判定，且 \(|S|\) 正好等于最优答案。

两边合并可得

\[ \mathrm{OPT}=\min_{\nu(S,R)=|R|}|S| \]

此处只需要求最优数量。若要从任意可行的 \(S\) 构造终止方案，还应执行第一点中的继续生长步骤。

普通二进制计数可能同时改变多个位。使用反射格雷码

\[ g(t)=t\mathbin{\oplus}\lfloor t/2\rfloor \]

按 \(t=0,1,\ldots,2^p-1\) 枚举，其中 \(\oplus\) 表示按位异或。相邻的编码恰好只差一个二进制位，所以每步只改变一株瓜藤是否在 \(S\) 内。例如三位的顺序是 000,001,011,010,110,111,101,100 .

对每块相关地维护计数 \(c_v\) ，表示它有多少株邻接瓜藤在 \(L\setminus S\) 中。于是 \(v\in R\) 当且仅当 \(c_v>0\) .一株瓜藤改变归属时，只更新它指定的至多四块地；计数跨过零时才增删对应的右部顶点。

因此，一次格雷码变化在 \(G[S,R]\) 中至多增删一个左部顶点和四个右部顶点。

始终维护当前图的一组最大匹配。增删一个顶点后，最大匹配大小最多变化一，具体处理如下：

操作	处理方法
插入顶点	从新顶点出发，寻找一条增广路；成功则匹配数加一。
删除未匹配顶点	直接删除，已有匹配仍为最大匹配。
删除已匹配顶点	先删除它的匹配边，再从它原来的搭档出发寻找一条增广路；成功则补回一条边。

搜索可以从左部或右部开始，沿“未选边、已选边”交替前进，到达另一侧的未匹配顶点时翻转整条路径。

插入顶点后，如果出现新的增广路，它必须以新顶点为端点；否则旧图中已经存在增广路。删除已匹配顶点后，如果还能恢复原匹配数，新的增广路必须以刚失去搭档的顶点为端点；否则它原本就存在。故每次至多做一次搜索，便能恢复最大匹配。

把每次集合变化拆成单个顶点的增删，并在每次增删后立即恢复最大匹配。处理完该株瓜藤及全部受影响地块后，再检查 \(\nu(S,R)=|R|\) 并更新答案。中途的图也保持匹配正确，但不作为候选集合判定。

实现可在另一部顶点已全部匹配时跳过插入后的搜索；删除匹配边后，若匹配数已经等于剩余两部大小的较小值，也无需搜索。跳过依据是匹配大小的上界，不改变判定条件。

设边数为 \(E\) ，只保留至少有一株邻接瓜藤的地块，则相关地块数至多为 \(E\le4p\) .一次增广搜索花费 \(O(p+E)=O(p)\) ；每步只有常数次顶点更新，总时间为 \(O(p2^p)\) ，空间为 \(O(p)\) .寻找格雷码变化位的简单循环也在这个时间界内。

若没有任何指定关系，答案直接为零。其余情况下，从 \(S=\varnothing\) 、空匹配、全部相关地块属于 \(R\) 开始维护。掩码使用无符号整数，本题 \(p\le24\) ；访问标记的最大更新次数也在有符号 32 位整数范围内。复杂度中的指数参数始终是瓜藤数 \(p\) .

小规模检查直接枚举全部匹配，并要求每条未选择的边至少有一个已匹配端点；穷举所有两部各三个顶点的图，再测试不等度数、孤立点与随机连接。来自小棋盘的实例还与《种西瓜 3》的轮廓线 DP、原《种西瓜》的两阶段匹配算法交叉核对。

参考程序见 std.cpp，数据范围与种子见生成计划。逐集合重建匹配的比较程序保留两阶段判定，用于性能对照。性能测量见评测环境与性能。