dinic 求最大流。
先引入两个概念:层次图、阻塞流。
层次图
根据每个点到源点的距离(到达源点最少要经过的边的数量),将点分层。
如图:
若level[s]=1,则各点上的数字就是该点的level。
一个bfs就行了。
不难发现,当层次图中不含有汇点时,就说明没有流可以流了。
阻塞流
就是一条不考虑反向边的极大流,每次流完一条阻塞流就一定会去掉一条边。
操作
先bfs建个层次图,然后dfs沿层次图一层一层传流量。
但为什么要这样?
因为
时间少啊!!!
首先,建层次图可以判断是否存在增广路。
其次,保证每次增广时间均不大于点数(层数最多就那么多)。
然后,dinic每次增广都可以将其中某一层连向下一层的边都流满,所以最多建$N$次层次图。
最后,dinic还可以进行当前弧优化,进一步压缩时间。
当前弧优化
在一次DFS中,当某个点所有流出的边都满了,就退出,不要再流这个点了。