种西瓜：题解¶
解法比较¶
出题人解法求最大产量时建立单位容量网络求最大匹配。求最小产量时按瓜藤递归：选择不产瓜，或选择一个尚空的相邻位置产瓜。若一株藤不产瓜，它的所有相邻位置最终都必须被其他藤占用，否则过程还未结束；剪枝搜索记录这些必占位置，以及剩余瓜藤能覆盖它们的数量，用于剪枝。终态正好枚举全部极大匹配，故取其中最小边数正确。每株藤至多四个邻点，不计剪枝的搜索上界为 \(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\) 中，为了让它停止生长，它的所有相邻空地都必须已被占用。令这些必须占用的空地组成集合
需要判断是否存在一个匹配，同时满足：
- 所有匹配边的瓜藤端都在 \(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。使用 C++17 编译后，可用 tests/generate.py --out-dir <题目目录以外的路径> --std <程序路径> 生成输入和答案。固定种子与用例目的见 生成计划。性能测量见 评测环境与性能。