二分图匹配与归约

先把问题说对

这一讲不从背模板开始，而是先问：输入是什么，需要输出什么，哪些输入合法，两个答案如何比较。对“二分图匹配与归约”先写一个只含数学对象的规格，再列空输入、单元素、重复元素、已有序和最坏构造。如果规格都含糊，后面的代码再快也无法验收。
（本段唯一反查锚：cs-28-algorithm-design-analysis/07/06/二分图匹配与归约。）

从朴素基线走到设计

先写一个明显正确的朴素方法，对一个只有10个元素的例子逐步执行，保留中间状态。然后标出重复工作、无用搜索和可以复用的子结果，这些证据才决定是用分治、贪心、动态规划、图搜索还是随机化。算法范式是对结构的回应，不是按关键词猜模板。
（本段唯一反查锚：cs-28-algorithm-design-analysis/07/06/二分图匹配与归约。）

对二分图匹配与归约先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例。设计完成后回到朴素基线，说清改进删掉了哪类工作，又引入了什么前提或额外空间。
（本段唯一反查锚：cs-28-algorithm-design-analysis/07/06/二分图匹配与归约。）

正确性不是“试出来的”

正确性证明分三层。首先证明局部操作保持不变量；其次证明过程会终止，递归规模严格下降或循环度量严格接近边界；最后证明终止时不变量与结束条件共同推出输出规格。贪心题要写安全选择或交换论证，动态规划要证明状态覆盖所有可行解且转移不重不漏。
（本段唯一反查锚：cs-28-algorithm-design-analysis/07/06/二分图匹配与归约。）

测试只能发现反例，不能替代对任意合法输入的证明。反过来，证明也不能代替实现测试：数组越界、整数溢出、索引错位和输入解析错误不会因为纸面证明正确就自动消失。
（本段唯一反查锚：cs-28-algorithm-design-analysis/07/06/二分图匹配与归约。）

复杂度要数真正的基本操作

选择与输入规模同步增长的基本操作，写出次数求和、递推式或期望。先给精确或可夹逼的表达式，再去掉常数和低阶项得到Theta级。时间和空间分开报告，预处理、单次查询、多次查询与输出大小分开报告。
（本段唯一反查锚：cs-28-algorithm-design-analysis/07/06/二分图匹配与归约。）

若某段代码的外层执行n次，内层第i次执行i次，总次数是1+2+…+n=n(n+1)/2，因而是Theta(n^2)，不是看到两层循环就盲猜n^2。对二分图匹配与归约还要区分最坏、平均、期望和摊还口径，不能混用。
（本段唯一反查锚：cs-28-algorithm-design-analysis/07/06/二分图匹配与归约。）

跟老师手算一次

用小输入建表：每行写当前子问题、已知信息、本次选择、新状态和不变量。图题记录队列或栈、已确定集和每条松弛；动态规划记录表格依赖与恢复指针；分治题画递归树；随机题固定随机源并保留轨迹。只有能预测下一步，才算真正理解算法。
（本段唯一反查锚：cs-28-algorithm-design-analysis/07/06/二分图匹配与归约。）

可运行实验与差分测试

为二分图匹配与归约实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率。代码题从标准输入读取，向标准输出写确定结果，不依赖本地文件、第三方包或不可控的时序。每道至少四组不同测试，并用朴素模型对小规模输入做差分比较。
（本段唯一反查锚：cs-28-algorithm-design-analysis/07/06/二分图匹配与归约。）

性能实验不只报一次最快时间。固定机器、解释器、编译参数和数据分布，预热后重复测量，同时记录基本操作次数。墙钟时间支持工程选择，操作计数支持渐近结论，两者不能互相冒充。
（本段唯一反查锚：cs-28-algorithm-design-analysis/07/06/二分图匹配与归约。）

反例、前提与失效边界

分析二分图匹配与归约时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。为当前方法写一个最小反例：改掉一个前提后，第一次错误选择或错误状态出现在哪里。常见错误是把局部最优当全局最优、忘记负权边、把可达当最短、把哈希相等当字符串相等，或在状态转移中重复/漏掉方案。
（本段唯一反查锚：cs-28-algorithm-design-analysis/07/06/二分图匹配与归约。）

跨章连接与自检

规格与证明是所有章的共同底座；分治和排序建立递归分析，贪心与动态规划建立最优性证明，图、流与字符串提供专门结构，随机和摊还扩展分析工具，NP完全与近似说明不能期待什么。为二分图匹配与归约写一条前置能力和一条它将支撑的后续算法。
（本段唯一反查锚：cs-28-algorithm-design-analysis/07/06/二分图匹配与归约。）

闭卷自检：能否不看答案写出规格，能否用不变量证明正确，能否数出时空复杂度，能否构造错误策略的最小反例，能否让参考实现通过新输入，能否说清结论只在什么前提下成立。
（本段唯一反查锚：cs-28-algorithm-design-analysis/07/06/二分图匹配与归约。）