Dinic是个很神奇的网络流算法。它是一个基于“层次图”的时间效率优先的最大流算法。层次图是什么东西呢？层次，其实就是从源点走到那个点的最短路径长度。于是乎，我们得到一个定理：从源点开始，在层次图中沿着边不管怎么走，经过的路径一定是终点在剩余图中的最短路。（摘自WC2007王欣上论文）注意，这里是要按照层次走。那么，MPLA（最短路径增值）的一大堆复杂的证明我就略掉了，有兴趣的请自行参阅WC2007王欣上神牛的论文。首先我们得知道，Dinic的基本算法步骤是，先算出剩余图，然后用剩余图算层次图，然后在层次图里找增广路。不知道你想到没有，这个层次图找增广路的方法，恰恰就是Ford-Fulkers

适合初学者看的网络流知识点大全文章目录网络流是什么网络流无权流Ford-Fulkerson算法算法思路算法展望最大流Dinic算法第一步：构建levelgraph第二步：构建residualgraph算法展望网络流是什么网络流是图论中一个非常重要的板块，也非常实用，经常在设计巴士路线，连接网线和运输水都有广泛运用，那为什么这样说呢，我们先来看一个例子在生活中，我们常常会遇到这样一类问题，我们要把水从S点运送到T点，其中有很多条道路，我们要经过不同的点最终到达T点，而每条道路都有一个他自己的最大容量，也就是说把水从这条管道运送时运送的数量不能超过他的容量，在这个基础上让我们求各种最值问题，因为这