<p>每个点的流量不平衡量 d[i] = sum_in_low - sum_out_low，即入边下界和减出边下界和；d[i] > 0 时从虚拟源点 SS 向 i 连容量 d[i] 的边，d[i] < 0 时从 i 向虚拟汇点 TT 连容量 -d[i] 的边。</p>
怎么算每个点的流量不平衡量 d[i]
核心是先“强行流满所有下界”，再看每个点因此多进或少出了多少流量。不直接建边，而是统计：对每个点 i，计算 d[i] = sum_in_low - sum_out_low，即所有指向 i 的边下界之和，减去所有从 i 出发的边下界之和。
常见错误现象：
- 把 d[i] 算反（比如写成 sum_out_low - sum_in_low），导致后续连边方向全错
- 忘记初始化 d[i] 为 0，残留脏数据
- 对无向边或双向边重复累加下界，误当两条有向边处理
使用场景：
- 所有上下界可行流建图的第一步，无论有源汇还是无源汇
- d[i] == 0 的点不用连虚拟边，可跳过
-
d[i] > 0：该点被强制流入更多，需从虚拟源点SS补d[i]流量 d[i] ：该点被强制流出更多，需流向虚拟汇点 <code>TT-d[i]流量- 所有
d[i] > 0的和一定等于所有d[i] 的绝对值之和（守恒），所以只需检查一边是否满流即可
虚拟源汇点 SS/TT 怎么连边、容量设多少
建图时新增两个点：SS = n + 1，TT = n + 2（假设原图点编号为 1..n）。只添加两类边：
常见错误现象：
- 把 SS → i 写成 i → SS，方向反了就完全无法平衡
- 容量设成 inf 而不是精确的 d[i]，导致满流判断失效
- 忘记给 SS 和 TT 单独编号，与原图点冲突（比如用 0 和 n+1 但没预留空间）
- 对每个
i满足d[i] > 0：调用add_edge(SS, i, d[i]) - 对每个
i满足d[i] ：调用 <code>add_edge(i, TT, -d[i]) - 原图每条边
(u, v)改为只保留上界冗余容量：add_edge(u, v, upp - low)，不再带下界
注意：add_edge 必须是双向边（正向边存容量，反向边存 0），否则 DFS/BFS 无法正确增广；若用 Dinic，还需保证链式前向星中反向边索引可快速定位（如 i^1）。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
为什么必须跑 SS→TT 最大流并验证满流
这个最大流不是最终答案，它只是“补平强制下界后剩余缺口”的搬运工。只有当所有从 SS 出发的边都跑满（即 cap[SS→i] == 0），才说明每个 d[i] > 0 的点都被补足，所有 d[i] 的点也都成功泄出——流量平衡达成。
立即学习“C++免费学习笔记（深入）”；
性能影响：
- 虚拟边总数 ≤ n，不会显著增加边数规模
- 但若 d[i] 极端不均（如一个点占总和 99%），可能造成层次图深度失衡，Dinic 效率下降
容易踩的坑：
- 验证时只查 SS 出边，却忽略反向边残量（正确做法是检查正向边容量是否为 0，而非反向边流量）
- 在跑完最大流后，未清空 SS 和 TT 的邻接表，导致后续（如有源汇最大流）复用图时出错
- 把 check() 写成遍历所有边，实际只需遍历 head[SS] 和 head[TT] 对应的出边
验证代码片段示意（Dinic 风格）：
bool check() {
for (int i = head[SS]; i; i = last[i])
if (cap[i]) return false;
return true;
}
有源汇时怎么复用这套虚拟源汇逻辑
有源汇图不能直接套用，因为原图的源点 S 和汇点 T 本身就不满足流量平衡（d[S] 为负大数，d[T] 为正大数）。解决方法是：先加一条 T → S 边，上下界为 [0, inf]，把原图“环化”成无源汇图，再走前述流程。
关键细节：
- 这条 T → S 边的下界是 0，所以不影响 d[i] 计算；上界是 inf，确保它不会成为瓶颈
- 加完这条边后，再重新计算全部 d[i]，此时 d[S] 和 d[T] 已被修正（因为 T → S 增加了 S 的入边下界、T 的出边下界）
容易被忽略的地方：
- 这条 T → S 边必须在计算 d[i] 之前加入，否则 d[S]/d[T] 仍失衡
- 后续求有源汇最大流时，要先删掉 T → S 边，再在残量网络上从原 S 到原 T 跑第二次最大流——第一次是找可行流，第二次才是榨干上限
