kőnig定理指出二分图最小点覆盖数等于最大匹配数，因其建模为流网络后，最小割仅由s→u'和v'→t边构成，对应点覆盖(u\u')∪v'；跑最大流后需在残量图中从s出发bfs得vis_s，最小点覆盖即为(u\vis_s)∪(v∩vis_s)。
二分图最小点覆盖为什么等于最大匹配
因为最小点覆盖数 = 最大匹配数，这是Kőnig定理的直接结论，而Kőnig定理本身是最大流最小割定理在二分图上的特例。关键在于建模方式：把二分图 G = (U, V, E) 转成流网络时，源点 s 连所有 U 中点（容量1），所有 V 中点连汇点 t（容量1），原边 u→v 改为 u→v 容量 +∞（或 ≥2 即可）。此时任意 s-t 割必然由三类边构成：s→U'、V'→t、U''→V'''，但后一类容量无穷大，所以最小割一定不切它——于是最小割只含 s→U\U₀ 和 V₀→t 边，对应一个点覆盖 (U\U₀) ∪ V₀；反过来每个点覆盖也能构造出等值割。
如何用Dinic或Edmonds-Karp求最小点覆盖的具体顶点集
跑完最大流后不能只看流量值，必须从残量图出发BFS/DFS找 s 可达点集：vis_s（从 s 出发沿残量 >0 的边能走到的点），然后最小点覆盖就是：(U \ vis_s) ∪ (V ∩ vis_s)。注意这里 U 和 V 是原始二分图的左右部，不是流网络中所有节点。
- 流网络节点编号需清晰区分：比如
s=0,U点编号1..|U|,V点编号|U|+1..|U|+|V|,t=|U|+|V|+1 - 残量图中，原边
u→v残量为cap[u][v] - flow[u][v]，反向边v→u残量即flow[u][v] - 只对
s做一次BFS，别误对t反向搜
常见错误：把最大流值当点覆盖顶点列表
最大流值只是最小点覆盖的大小（即 |C|），不是点集本身。有人直接取所有满流的 s→u 或 v→t 边对应的端点，这是错的——例如某 u∈U 的出边满流，但若 u 在 vis_s 中，它就不该被选入覆盖（因为 U \ vis_s 才是选中的左部点）。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 错误示例：输入边
(u1,v1), (u1,v2), (u2,v1)，最大匹配为2，但仅选u1和v1不覆盖(u2,v1)—— 正确覆盖是{u1, v1}或{u2, v2}，必须依赖残量连通性判断 - 混淆
vis_s和 “有流量流入/流出” 的节点：一个v∈V可能有入流但不在vis_s中（比如其上游u未被s到达），这时它就不属于覆盖
建图时容量设为1还是INF的实质影响
U→V 边容量必须 ≥2（通常设 INT_MAX 或一个大于 min(|U|,|V|) 的数），否则最小割可能被迫切这些边，破坏与点覆盖的一一对应。而 s→U 和 V→t 必须严格为1，否则最大流值会失真（比如设成2，就可能让一个 u “承担”两个匹配，实际并不存在）。
- 若误将
U→V边设为1，且存在长度为4的增广路（s→u1→v1→u2→v2→t），算法可能切u1→v1边，导致割值虚高 - 若
s→u容量为2，而u只连一个v，则最大流可能为2但实际最大匹配仍为1，Kőnig定理失效
真正容易被忽略的是残量图遍历的方向和范围——它只在构造好的流网络上做一次正向BFS，且必须包含所有节点类型（s, U, V, t），但最终只从结果里提取 U 和 V 中的子集。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
