前置知识
引入
我们举个例子吧：
有一个毒瘤水管工，他会造水管，有一天他造了一个水管网络，就像一个图。其中有一个点只有出边，就是起点，还有一个点只有入边，是终点。
点之间有一些管子，这些管子都有单位时间内的容量，现在毒瘤水管工想知道，他的管子在单位时间内在起点终点之间最多能流多少水。
概念
- 源点：顾名思义，起点，一般用s表示
- 汇点：顾名思义，终点，一般用t表示。。。
- 容量：顾名思义。。。一条边单位时间内的的容量
- 残余网络：进行增广后剩余的网络
- 増广：
増广就是在残余网络中寻找从源点到汇点的可行路径（増广路），并将该路径上的所有边的容量减去路径中的最小容量，形成新的残余网络，人话就是找一条能走的路，然后把路走掉。
例如：
如果当前有这样一个残余网络，那么就是一条増广路，最小容量是4，进行増广过后就形成了这样一张图：
如何寻找増广路？直接dfs即可。
- 反向边：
有时候，程序増广的时候会出现爆炸性错误，例如还是那个图：
有两条増广路，万一程序选错了怎么办？
这时就要请出反向边了。
每次増广的时候，在残余网络上逆着増广路径建容量与増广路径最小容量相等的反向边，比如刚才那张图，就顺着建容量为4的边。相当于把原来的那条路抵消掉了，如果増广时走过了反向边，就相当于把原来的増广撤回去了。
这就给了程序一个反悔的机会。
朴素算法
- 増广
- 沿着増广路径建反向边
- 如果源点与汇点依然连通，回到1
Dinic优化
Dinic的优化就是用bfs建立了由s开始的一个分层图，每次寻找増广路时必须让边上的层数严格递增，就可以确保每一步都离汇点近了一些这样就不会陷入毒瘤数据卡成的死循环，比如这样的著名毒瘤数据：
在这个数据中，如果用朴素算法，就会让中间容量为1的边上下抖动抽搐，等到他抽了999次的时候才把上面和下面的999减没。如果用Dinic，两次直接求出999+999。