Dinic算法是最大流问题的经典算法，源自于一种称为Ford-Fulkerson方法的思想。
Ford-Fulkerson方法的核心思想和Floyd-Warshall算法相似，使用一种浪淘沙式地筛选策略。这里不求一步到位，但求不断地从残图中找到可行路径以榨取剩余流量。
func (ctx *contextL) dinic() uint {
flow := uint(0)
for ctx.separate() { //抽取子图（层次图）
flow += ctx.search() //从子图中榨取剩余流量
ctx.flushBack() //残图整合（将榨干的子图合并回母图）
}
return flow
}为了方便剥削，Dinic算法引入了等级制度，先把点分成三六九等，然后按阶层逐级征收。虽然同一阶层的点暂无往来，但由于每轮征收过后总有一些关系破裂（边断掉），等级会因此重新洗牌，所以任何关系最终都不会漏网。
A
A |
/ \ D
A - B - E B D A B - E / \
| / | / | => / \ / | / / | => B C
D - C - Z E C D - C Z \ /
\ / E
Z |
Z
阶层分化过程采用宽度优先搜索，再排除掉暂时没有利用价值的点：
func (ctx *contextL) separate() bool {
if !ctx.markLevel() { //标记节点层次
return false
}
for curr := 0; curr < len(ctx.level); curr++ {
if ctx.level[curr] == fakeLevel {
continue
}
paths := ctx.origin[curr]
for i := 0; i < len(paths); i++ {
next := paths[i].Next
if ctx.level[next] == ctx.level[curr]+1 {
ctx.shadow[curr] = append(ctx.shadow[curr], paths[i])
paths[i].Weight = 0 //将主图内容抽取到残图
} } }
return true
}我们采用深度优先搜索，试探是否有可以搜刮的路径：
func (ctx *contextL) search() uint {
for flow, stream := uint(0), uint(0); ; flow += stream { //每一轮都至少会删除图的一条边
stream = math.MaxUint
ctx.stack.Clear()
for curr := ctx.start; curr != ctx.end; {
sz := len(ctx.shadow[curr])
if sz != 0 { //可通
ctx.stack.Push(memo{idx: curr, stream: stream}) //下探
path := ctx.shadow[curr][sz-1]
curr, stream = path.Next, utils.Min(stream, path.Weight)
} else { //碰壁，退一步
if ctx.stack.IsEmpty() { return flow } //退无可退
tmp := ctx.stack.Pop()
curr, stream = tmp.idx, tmp.stream
last := len(ctx.shadow[curr]) - 1
fillBack(ctx.origin[curr], ctx.shadow[curr][last])
ctx.shadow[curr] = ctx.shadow[curr][:last]
}
}
for !ctx.stack.IsEmpty() { //处理找到的增广路径
tmp := ctx.stack.Pop()
curr := tmp.idx
last := len(ctx.shadow[curr]) - 1
path := &ctx.shadow[curr][last]
path.Weight -= stream //抽出顺流
ctx.reflux[path.Next] = append(ctx.reflux[path.Next],
graph.Path{Next: curr, Weight: stream}) //添加逆流容限，防止贪心断路
if path.Weight == 0 {
ctx.shadow[curr] = ctx.shadow[curr][:last] //剔除无效残边
} } } }这里有一点要注意，有些时候切断边会意外破坏图的连通性。物理上，不存在管道消失一说，今后显然还可以引入逆流来抵消本次的流选择。而在算法中，我们也要给予相应的支持。
A → C → D A C → D A C → D
↓ ↓ ↓ => ↓ ↓ =(fix)=> ↓ ↑ ↓
B → E → F B → E F B → E F
我们看到Dinic算法的核心是抽取子图、榨取剩余流量以及残图整合这三个操作的循环。
其中，榨取剩余流量的过程包括试探和整理两部分。一次整理需要遍历记录栈，操作次数为O(V)级，同时至少删除子图中的一条边。整理过程对边的删除是试探成功的结果，另一方面，试探失败也会逐渐删除子图里无效路径中的边，故试探过程总是会删除子图中的边。由此可以推知，驱动试探过程的三重循环累计执行次数为O(E)，而其中最外层循环的执行次数必然小于O(E)。
基于二分查找的残边回收操作的复杂度为O(logV)，基于归并的图整合操作的复杂度为O(E)。另外，抽取子图的复杂度是O(E)。最后，我们不难算出Dinic算法的复杂度为O(E/k) × (O(E) + O(kV) × O(logV) + O(kV + E)) = O(V2E)。