最大流最小割：把约束系统翻译成一张网络

核心洞察：最大流的重点不在 Dinic 模板，而在于识别哪些对象是流、哪些限制是容量、哪些选择可以由割来表达。 霓虹港夜间要为维修队分配有限的检修窗口：每台设备最多安排一次，工程师每天能处理的任务数有限，某些资质与设备类型必须匹配。这类“选择很多、限制相互耦合”的问题，常常可以变成一张从源点流向汇点的网络。

残量网络是一种允许后悔的结构

若一条边容量为 3，当前流量为 2，正向还可通过 1 单位流；更重要的是，反向边容量为 2，意味着之后可以撤销已做出的局部选择。没有反向边，贪心地占用一条边后就无法修正，算法也无法保证最优。 增广路每次都把更多流送到汇点；当不存在增广路时，源点可达集合与不可达集合之间的边构成一个割。最大流最小割定理说：此时已经没有任何更便宜的“通道组合”可以把更多资源从源送到汇。

Dinic 为什么更快

Dinic 先用 BFS 建立分层图，只沿着距离递增的边寻找路径；再用 DFS 在本轮层级中尽可能送出阻塞流。当前弧优化记住每个点已检查到的边，避免反复从头扫描。

struct Edge { int to, rev; long long cap; };
vector<Edge> graph[MAXN];
int level[MAXN], work[MAXN];

void addEdge(int from, int to, long long cap) {
    graph[from].push_back({to, (int)graph[to].size(), cap});
    graph[to].push_back({from, (int)graph[from].size() - 1, 0});
}

DFS 推流时必须同时更新正向残量与反向残量。这一对更新正是“可撤销选择”的代码化表达。

建模的四个提问

1. 谁是流的单位？ 可能是一名工程师、一次匹配或一个可选项目。
2. 容量限制在哪里？ 设备、人员、时间段或预算都可能成为边容量。
3. 选择之间如何互斥？ 用中间点和容量 1 的边表达不可重复选择。
4. 答案的割意味着什么？ 它往往直接解释瓶颈集合。 二分图匹配是网络流的特殊情形：左侧到右侧的边容量为 1。项目选择问题则能用源边表达收益、汇边表达成本、依赖关系用无穷容量边约束。

复杂度与边界

一般网络上的 Dinic 最坏复杂度为 O(V^2E)，但在单位网络、二分图等结构中表现更好。若边带费用而不是只有可行性，应考虑最小费用最大流；若问题本质是割而非流量，也可直接从最小割角度建模。

易错点

• 反向边下标和容量更新不对称，结果会悄悄错误。
• int 容量溢出，累计流量应使用 long long。
• 把“价值最大化”误当作纯最大流，忽略了费用或收益转换。

结语

网络流真正训练的是翻译能力：把自然语言中的资格、名额、依赖和冲突，翻译成节点、边、容量和割。模板只是最后一公里。