网络流

Dinic 算法

Java

最大流的经典算法。使用 u.add(v, cap) 加一条从点 u 到点 v 的边，容量为 cap。建图后调用 dinic(s, t) 得到从源点 s 到汇点 t 的最大流。

内部原理

dinic(s, t) 首先构造从 s 到 t 的分层图，使用 level 表示点的层次。然后不断调用 dfs 从 s 到 t 推流，流量只从 k 层流向 k+1 层。