C++平面图转对偶图怎么快速求解最小割-C++-PHP中文网

平面图最小割等于对偶图最短路，因为原图任意s-t割一一对应对偶图中s到t的路径，且割容量和等于路径边权和；前提为连通平面图、s与t位于同一外部面（否则需加辅助边调整），构建时用半边结构按面定向连边，dijkstra求最短路即得最小割值。

c++平面图转对偶图怎么快速求解最小割

平面图最小割为什么能转成对偶图最短路

因为平面图的任意 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++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

示例片段：

vector<vector 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)
</vector>