Loading...
Dinic 算法 首先我们需要明确：Ford-Fulkerson 的思想是很好的，但是如果直接猛干，这个复杂度暴涨，而且是时候祭出这张经典的图了： 复杂度会飙升到 $O(E\max |f|)$。 那 Dinic 算法做了什么呢？ 多路增广：找增广路时进行 DFS，这就意味着，如果找到了一条增广路但是流量却还没有被用完，那就用剩余的流量再找一条！ 最短增广：每次先用 BFS 做分层，算出每...
Preface 证明思路 Q&A 网络流的定义 网络流的性质 最大流解决的问题 Ford-Fulkerson方法 残存网络 增广路径 网络流的切割 最大流最小割定理 Ford-Fulkerson 算法 Preface 本文为我初三下时学习网络流的笔记整理，大多源自算法导论。当时学习的是网络流代数法建模。（手动@金牌教练） 证明思路 明确 Ford-Fulkerson 算法的...