网络流与最大流
一句话说明
最大流就是在每条边容量限制内，尽可能多地把流量从源点送到汇点；Dinic 的关键是“分层图 + 阻塞流”。
先别急着上公式，先看它在算什么
图上的每条边都有一个容量上限：
- 这条边最多能送多少流
同时除了源点和汇点之外，还要满足流量守恒：
- 流进多少，就必须流出多少
所以最大流问题问的是：
在这些容量约束下，s 到 t 最多能送多少总流量？为什么“残量网络”是灵魂
很多人第一次学最大流会觉得奇怪：
为什么已经走过的边，还要建反向边？因为算法前面做的选择，后面未必最优。
反向边的作用就是：
- 允许撤销一部分旧流量
- 让这部分流改走更好的路径
所以残量网络维护的是两件事：
- 这条正向边还能再送多少
- 这条已经送过的流还能退回来多少
Dinic 的核心流程
每一轮做两步：
- BFS 建分层图
- DFS 在分层图里不断送阻塞流
分层图在干什么
它把图按“离源点的层数”分层，只保留：
第 k 层 -> 第 k+1 层的可行边。
这样 DFS 送流时就不会乱绕回头路。
阻塞流在干什么
在当前分层图里，尽量把还能增广的流都送满。
直到本轮再也送不动，才重新 BFS 建下一张分层图。
Go 代码：Dinic 模板
type FlowEdge struct {
To int
Rev int
Cap int
}
type Dinic struct {
Graph [][]FlowEdge
Level []int
Iter []int
}
func NewDinic(n int) *Dinic {
return &Dinic{
Graph: make([][]FlowEdge, n),
Level: make([]int, n),
Iter: make([]int, n),
}
}
func (d *Dinic) AddEdge(from, to, cap int) {
forward := FlowEdge{To: to, Rev: len(d.Graph[to]), Cap: cap}
backward := FlowEdge{To: from, Rev: len(d.Graph[from]), Cap: 0}
d.Graph[from] = append(d.Graph[from], forward)
d.Graph[to] = append(d.Graph[to], backward)
}
func (d *Dinic) bfs(s, t int) bool {
for i := range d.Level {
d.Level[i] = -1
}
d.Level[s] = 0
queue := []int{s}
for len(queue) > 0 {
v := queue[0]
queue = queue[1:]
for _, e := range d.Graph[v] {
if e.Cap <= 0 || d.Level[e.To] != -1 {
continue
}
d.Level[e.To] = d.Level[v] + 1
queue = append(queue, e.To)
}
}
return d.Level[t] != -1
}
func (d *Dinic) dfs(v, t, f int) int {
if v == t {
return f
}
for ; d.Iter[v] < len(d.Graph[v]); d.Iter[v]++ {
i := d.Iter[v]
e := &d.Graph[v][i]
if e.Cap <= 0 || d.Level[e.To] != d.Level[v]+1 {
continue
}
pushed := d.dfs(e.To, t, min(f, e.Cap))
if pushed > 0 {
e.Cap -= pushed
rev := e.Rev
d.Graph[e.To][rev].Cap += pushed
return pushed
}
}
return 0
}
func (d *Dinic) MaxFlow(s, t int) int {
flow := 0
const inf = int(1e18)
for d.bfs(s, t) {
for i := range d.Iter {
d.Iter[i] = 0
}
for {
pushed := d.dfs(s, t, inf)
if pushed == 0 {
break
}
flow += pushed
}
}
return flow
}
func min(a, b int) int {
if a < b {
return a
}
return b
}这个模板里最重要的三个不变量
1. 只在残量大于 0 的边上走
没有剩余容量的边，不可能再送流。
2. DFS 只沿分层图向下走
也就是：
level[next] = level[cur] + 1这样可以避免在一轮里绕来绕去。
3. 送出多少流，就把反向边容量加回来多少
这一步就是“撤销能力”的来源。
为什么当前弧优化能提速
Iter[v] 表示：
节点 v 的边已经试到哪一条了如果某条边在这一轮分层图里已经证明确实送不动，就没必要每次 DFS 又从头重试一遍。
这就是当前弧优化的意义。
最大流最小割为什么总一起出现
因为有一个核心结论：
最大流的值 = 最小割的容量也就是说，当残量网络里再也找不到从源点到汇点的可行路时：
- 还能从源点到达的点构成集合
S - 剩下的点构成集合
T
原图中从 S 指向 T 的边，就是一个最小割。
常见建模
- 二分图最大匹配
- 人和任务分配
- 边容量表示资源上限
- 最少切断多少容量才能隔开两侧
很多题表面看不是“流”，但只要出现：
- 资源分配
- 容量限制
- 多源多汇可转换
就值得往网络流上想。
易错点
Dinic 最容易错的地方
- 反向边索引必须和正向边成对维护。
- DFS 只能沿
level + 1的方向走。- 每轮重新 BFS 后，要把当前弧数组
Iter重新清零。- 容量和答案可能很大，注意整数范围。
复杂度
普通 Dinic 在一般图上的常见上界可记为：
O(V^2 E)实际做题时通常比这个上界快很多。