平面图最小割等于对偶图最短路，因为原图任意s-t割一一对应对偶图中s到t的路径，且割容量和等于路径边权和；前提为连通平面图、s与t位于同一外部面（否则需加辅助边调整），构建时用半边结构按面定向连边，Dijkstra求最短路即得最小割值。
平面图最小割为什么能转成对偶图最短路
因为平面图的任意 s-t 割对应对偶图中一条从 s* 到 t* 的路径，且割的容量和等于该路径边权和。这个等价性成立的前提是：原图是**连通平面图**、有明确的外部面、且 s 和 t 都在外部面上（或可通过加边调整到同一面）。不满足时，强行建对偶图会导致路径漏掉关键割边，结果错误。
常见错误现象：min_cut = 0 但实际有正容量割；或最短路结果明显偏小。往往是因为没把 s 和 t 放在同一外部面——此时需先对面进行重定向，或在原图外围加一圈无穷大容量边，强制统一外部面。
怎么构建对偶图（C++ 实操要点）
核心不是“画出对偶点再连边”，而是用面遍历 + 边定向来生成对偶边。推荐用 half-edge（双向边）结构存原图，每条有向边 e 属于唯一左侧面 f_left，其反向边 e^rev 属于右侧面 f_right。对偶图中，f_left → f_right 连一条权为 e.cap 的边。
- 必须给每个面编号，可用 DFS 遍历未访问的半边来识别面（注意处理桥边：桥的两侧是同一个面，此时不加对偶边，或加自环但后续忽略）
-
s和t所在面要标记为s*和t*；若它们本不在同一面，就人为添加一条绕外侧的“辅助边”，容量设为极大值（如INT_MAX/2），再重新剖分面 - 对偶图边数 ≤ 原图边数，但可能含重边——合并时取最小容量，否则 Dijkstra 会误判
Dijkstra 求最短路时要注意什么
对偶图边权全非负（原图容量 ≥ 0），所以用朴素 Dijkstra 即可，不用 Bellman-Ford。但容易踩的坑在于：顶点数可能是 O(E) 级别（面数最多为 E - V + 2），别用 vector<vector int>>></vector> 存稠密对偶图——很多面对之间根本无边，应只存实际生成的边，用 vector<vector int>>></vector> 按面索引建邻接表，空间可控。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
示例片段：
vector<vector<pair<int, int>>> dual_adj(face_cnt);
for (each half-edge e) {
int f1 = face_id[e.left_face], f2 = face_id[e.rev.left_face];
if (f1 != f2) dual_adj[f1].emplace_back(f2, e.cap);
}
// 然后跑 Dijkstra(dual_adj, s_star, t_star)
边界与退化情况怎么处理
原图不连通？对偶图会分裂，s* 和 t* 可能不可达——此时最小割为 0（无需割边即可分离）。原图有重边？每条边独立生成对偶边，没问题。原图有自环？自环不划分新面，对应对偶图无边，直接忽略。
最容易被忽略的是：**对偶图最短路经过的边数，等于原图割边数，但路径上的边权和才是最小割值**。有人误以为“边数最少”就是最小割，这是错的——权重才决定容量和。另外，如果最小割不唯一，Dijkstra 返回任意一条最短路即可，对应任一最小割方案。
