Dinic

dinic 求最大流。

先引入两个概念:层次图、阻塞流。

层次图

根据每个点到源点的距离(到达源点最少要经过的边的数量),将点分层。

如图:

dinic

若level[s]=1,则各点上的数字就是该点的level。

一个bfs就行了。

不难发现,当层次图中不含有汇点时,就说明没有流可以流了。

阻塞流

就是一条不考虑反向边的极大流,每次流完一条阻塞流就一定会去掉一条边。

操作

先bfs建个层次图,然后dfs沿层次图一层一层传流量。

但为什么要这样?

因为

时间少啊!!!

首先,建层次图可以判断是否存在增广路。

其次,保证每次增广时间均不大于点数(层数最多就那么多)。

然后,dinic每次增广都可以将其中某一层连向下一层的边都流满,所以最多建$N$次层次图。

最后,dinic还可以进行当前弧优化,进一步压缩时间。

当前弧优化

在一次DFS中,当某个点所有流出的边都满了,就退出,不要再流这个点了。

例题:POJ1273题解戳这