知识点总结

1. 匹配与增广路

• 匹配是图中两两无公共端点的边集；交错路是匹配边与非匹配边交替出现的路，增广路是两端均未匹配的交错路，沿增广路取反可使匹配数增加 1。
• Berge 引理：匹配最大当且仅当不存在增广路，通过对称差引理证明。
• 二分图匹配中，从未匹配左部点出发沿非匹配边、匹配边交替搜索，到达未匹配右部点即找到增广路。

2. Kuhn 算法（二分图最大匹配）

• 对每个左部点尝试增广，DFS 依次访问非匹配边，若右部点未访问，则尝试将其匹配或递归增广其当前配偶。
• 每次增广成功则匹配数加 1，时间复杂度 $O(|X||E|)$，空间 $O(|V|+|E|)$。

3. Hopcroft-Karp 算法

• 通过 BFS 构建当前最短增广路的分层图，然后在分层图上 DFS 找一组点不交的最短增广路（阻塞流），同时取反。
• 一阶段 $O(m)$，总阶段数为 $O(\sqrt{n})$，总时间复杂度 $O(m\sqrt{n})$，空间 $O(n+m)$。

4. König 定理与最小点覆盖、最大独立集

• 二分图最大匹配大小等于最小点覆盖大小；构造方法：从所有未匹配左部点沿交错图可达集合 $Z$，则最小点覆盖为 $(X\setminus Z)\cup(Y\cap Z)$。
• 最大独立集大小为 $|V|-$ 最大匹配，由点覆盖补集给出。

5. DAG 最小路径覆盖与 Dilworth 定理

• 将 DAG 每个点拆为左右两部，原边 $u\to v$ 连 $u_L\to v_R$，最大匹配数 $m$，最小路径覆盖为 $|V|-m$。
• 偏序集最长反链等于最小链划分，通过拆点图最小点覆盖构造反链证明。

6. Hall 定理及其缺陷公式

• 二分图存在覆盖 $X$ 的匹配当且仅当任意 $S\subseteq X$ 有 $|N(S)|\ge |S|$。
• 最大匹配覆盖的左部点数为 $|X|-\max_{S\subseteq X}(|S|-|N(S)|)$，缺陷集合可由交错可达集给出。

7. 最大权完美匹配（KM 算法）

• 给每个点设可行顶标 $l_x+l_y\ge w_{x,y}$，相等子图为满足等号的边；若相等子图有完美匹配，则其权值等于顶标和，即为最大权。
• 从未匹配左部点出发，在相等子图中找增广路；若失败则调整顶标，减小 $S$ 侧、增大 $T$ 侧，加入新的紧边，反复直到增广。
• 用 slack 优化后单次增广 $O(n^2)$，总时间复杂度 $O(n^3)$，空间 $O(n^2)$。

8. 最大流基本概念与增广路

• 流网络含容量 $c(u,v)$，流 $f$ 满足反对称、容量限制、中间点守恒；流值为源点净流出。
• 残量网络 $c_f=c-f$，沿残量路径增广可增加流值；最大流当且仅当残量网络无 $st$ 路径。
• 最大流最小割定理：最大流值等于最小割容量。

9. 流分解

• 任意非负流可分解为若干 $st$ 路径流与圈流之和，整数流可整数分解。

10. 平面图最小割转最短路

• 平面图 $st$ 最小割等于其对偶图中相应两个外部面点之间的最短路，用 Dijkstra 求解。

11. 最小割树（Gomory-Hu 树）

• 构造一棵带权树，使得任意两点间的最小割等于树上路径的最小边权。
• 通过递归分裂袋（顶点集），每次取袋内两点求 torso 最小割，将袋分裂为两部分，重新连接邻袋；共 $n-1$ 次最大流，总时间 $O(n\cdot \text{MF}(n,m))$。

12. Edmonds-Karp 与 Dinic 算法

• Edmonds-Karp：每次 BFS 选最短增广路，增广次数 $O(VE)$，总 $O(VE^2)$。
• Dinic：BFS 分层，DFS 找阻塞流，当前弧优化，每轮 $O(VE)$，总 $O(V^2E)$，空间 $O(V+E)$。

13. 最小费用最大流与 SSP

• 费用流中沿残量网络的最短（单位费用最小）$st$ 路增广，可保持同流值下的最优性；若初始无负圈，则增广后也无负圈。
• 任意流量目标时，当前最短路径原费用非负则停止。

14. 势能优化（Primal-Dual）

• 定义约化费用 $w_h(u,v)=w(u,v)+h_u-h_v$，路径费用与原费用相差 $h_s-h_t$，环费用不变。
• 维护势能 $h$ 使所有正残量位置约化费用非负，则可用 Dijkstra 求最短路；增广后更新 $h_v\leftarrow h_v+\delta_v$，保持非负性。
• 每轮 $O(E\log V)$，增广 $K$ 轮总 $O(K E\log V)$，空间 $O(V+E)$。

15. 费用流的凸性

• 最小费用 $C(F)$ 作为流值 $F$ 的函数是离散凸的（整数容量）或分段线性凸（实容量），相邻流值的差分（即单位增广路费用）单调不降。

16. 应用：质因数分解匹配（最大流）

• 多个数之间的操作可分解为质因子，对每个质数建二分图（奇偶下标），源/汇侧容量为指数，给定对连无限边，最大流即为该质数的操作次数，累加所有质数。

17. 应用：K 条路径最大点权和（费用流）

• 缩 SCC 成 DAG，每个点拆为入出，内部连两条边：容量 1 费用 $-W_v$（收益）和容量 $K-1$ 费用 0，DAG 边容量 $K$ 费用 0；求流值 $K$ 的最小费用流取负。

18. 应用：曼哈顿距离最大匹配（费用流）

• 利用 $|x-x’|+|y-y’|=\max_{\sigma,\tau}(\sigma x+\tau y-\sigma x’-\tau y’)$，建四层图：红点连四个符号节点，符号节点连蓝点，容量为数量，费用为对应线性式；求固定流量的最大费用流（取负求最小费用）。

今日题目总结

无，因为我今天全写的模板题QwQ