标签 Dinic 下的文章

最大流的优化——Dinic算法

Dinic 算法 首先我们需要明确：Ford-Fulkerson 的思想是很好的，但是如果直接猛干，这个复杂度暴涨，而且是时候祭出这张经典的图了： 复杂度会飙升到 $O(E\max |f|)$。 那 Dinic 算法做了什么呢？ 多路增广：找增广路时进行 DFS，这就意味着，如果找到了一条增广路但是流量却还没有被用完，那就用剩余的流量再找一条！ 最短增广：每次先用 BFS 做分层，算出每...