# 种西瓜：题解

## 解法比较

出题人解法求最大产量时建立单位容量网络求最大匹配。求最小产量时按瓜藤递归：选择不产瓜，或选择一个尚空的相邻位置产瓜。若一株藤不产瓜，它的所有相邻位置最终都必须被其他藤占用，否则过程还未结束；剪枝搜索记录这些必占位置，以及剩余瓜藤能覆盖它们的数量，用于剪枝。终态正好枚举全部极大匹配，故取其中最小边数正确。每株藤至多四个邻点，不计剪枝的搜索上界为 $O(5^p)$ ，辅助空间为 $O(V+p)$ ，其中 $p$ 为藤数、$V$ 为格子数。

Codex（GPT-6）采用的实现枚举产瓜藤集合 $S$ ，把未产瓜藤的所有邻点设为必须占用的位置，再用匹配检查能否同时覆盖 $S$ 和这些位置，完整等价证明见下文。最小值阶段为 $O(2^p(V+p^2))$ 时间、$O(V+p)$ 空间。它减少枚举分支并使终态条件直接可证，但每个集合都要运行匹配；剪枝搜索可能更快，未做速度对比。最大值仍是最大匹配问题。

## 把生长过程看成匹配

以瓜藤为左部、初始空地为右部，相邻的瓜藤与空地之间连边。一次结瓜选择一条边；每株瓜藤和每块空地都至多使用一次，因此最终结果是一组匹配。

生长终止等价于不存在两端都未匹配的边，也就是匹配已经**极大**。极大表示不能再直接加入一条边，不等于边数最多的**最大匹配**。反过来，任意极大匹配都能实现：让其中各条边对应的瓜藤依次结瓜，互不冲突；完成后也没有其他生长机会。

## 求最多结瓜数

最大匹配一定极大，因此求二分图最大匹配即可。逐个尝试左部顶点，用增广路重新安排已有匹配。每成功增广一次，匹配数增加一；不存在增广路时得到最大匹配。

## 求最少结瓜数

设瓜藤数为 $p$ .枚举集合 $S$ ，表示恰好哪些瓜藤最终结瓜。若瓜藤不在 $S$ 中，为了让它停止生长，它的所有相邻空地都必须已被占用。令这些必须占用的空地组成集合

$$R=N(\overline S)$$

需要判断是否存在一个匹配，同时满足：

- 所有匹配边的瓜藤端都在 $S$ 中；
- 覆盖 $S$ 中每株瓜藤；
- 覆盖 $R$ 中每块空地。

若 $|R|>|S|$ ，直接排除。否则分两步匹配：先把 $R$ 看作增广路起点，只向 $S$ 中的瓜藤连边，尝试覆盖整个 $R$ ；再从 $S$ 中尚未匹配的瓜藤出发，尝试向所有空地增广，覆盖整个 $S$ .

第二步不会破坏第一步：增广路的内部顶点只是更换搭档，原来已匹配的顶点不会变成未匹配。若确实存在同时覆盖两边指定集合的匹配，第一步得到的任意匹配都能用增广路扩展到大小 $|S|$ ，且一直保留 $R$ 的覆盖。因此这两步的判定是充分且必要的。

通过判定的匹配恰有 $|S|$ 条边，且每株未结瓜瓜藤的邻居均已占用，所以它是极大匹配。对所有可行集合取最小 $|S|$ 即为答案。最大匹配的大小可作为初始上界；不必检查不能改进答案的集合。

## 复杂度与实现

令 $V=nm$ .每株瓜藤最多连四条边，故边数 $E\le4p$ .最大值部分的时间为 $O(V+pE)=O(V+p^2)$ .最小值部分枚举 $2^p$ 个集合，每个集合的建表和匹配花费 $O(V+p^2)$ ，总时间为 $O(2^p(V+p^2))$ .两部分空间均为 $O(V+p)$ .

最小值数据保证 $p\le18$ .没有瓜藤或没有空地时，答案都是零。参考程序只对最小值部分使用集合位掩码；最大值部分不受位掩码位宽限制。

## 验证

独立检查器枚举所有 $2\times3$ 三状态棋盘，再直接枚举所有匹配并检查是否终止，同时核对最大值与最小值；另外加入随机小棋盘。这个模型不使用集合 $S$ 的两步匹配判定。

## 程序与复现

参考程序见 [std.cpp](std.cpp)。使用 C++17 编译后，可用 `tests/generate.py --out-dir <题目目录以外的路径> --std <程序路径>` 生成输入和答案。固定种子与用例目的见 [生成计划](tests/plan.json)。性能测量见 [评测环境与性能](../../../docs/评测环境与性能.md)。