第12章笔记：网络流、匹配与赛场综合

目标

把增广、不变量、压力测试和时间分配整合成比赛能力。

七课依赖

• 残量网络与增广路：围绕残量网络与增广路先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：流量模型必须满足容量与守恒；二分图匹配建图方向不能错。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• Dinic分层图：围绕Dinic分层图先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：流量模型必须满足容量与守恒；二分图匹配建图方向不能错。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 二分图匹配：围绕二分图匹配先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：流量模型必须满足容量与守恒；二分图匹配建图方向不能错。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 最小割与建模：围绕最小割与建模先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：流量模型必须满足容量与守恒；二分图匹配建图方向不能错。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 题目组合与部分分：围绕题目组合与部分分先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：流量模型必须满足容量与守恒；二分图匹配建图方向不能错。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 压力测试和对拍器：围绕压力测试和对拍器先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：流量模型必须满足容量与守恒；二分图匹配建图方向不能错。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 整场模拟、复盘与知识地图：围绕整场模拟、复盘与知识地图先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：流量模型必须满足容量与守恒；二分图匹配建图方向不能错。 本课必须再检查边界输入、整数溢出、下标和不可行状态。

复杂度与适用条件表

算法对象	不变量/复杂度来源	使用边界
残量网络与增广路	围绕残量网络与增广路先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	流量模型必须满足容量与守恒；二分图匹配建图方向不能错。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
Dinic分层图	围绕Dinic分层图先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	流量模型必须满足容量与守恒；二分图匹配建图方向不能错。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
二分图匹配	围绕二分图匹配先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	流量模型必须满足容量与守恒；二分图匹配建图方向不能错。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
最小割与建模	围绕最小割与建模先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	流量模型必须满足容量与守恒；二分图匹配建图方向不能错。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
题目组合与部分分	围绕题目组合与部分分先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	流量模型必须满足容量与守恒；二分图匹配建图方向不能错。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
压力测试和对拍器	围绕压力测试和对拍器先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	流量模型必须满足容量与守恒；二分图匹配建图方向不能错。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
整场模拟、复盘与知识地图	围绕整场模拟、复盘与知识地图先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	流量模型必须满足容量与守恒；二分图匹配建图方向不能错。 本课必须再检查边界输入、整数溢出、下标和不可行状态。

复盘

每题保存暴力、优化、证明、四组边界测试和首个WA输入；一周后换数据重做。