最大流

问题:给你一幅网络图,每条边上有最大流量限制,问从源点s到汇点t的最大流量.

• 增广路: 从源点s到汇点t的一条变权都为正的路径.
• 反向弧: 用于纠正错误的寻找增广路的一种机制,也就是给一个后悔的机会.其实这个东西,有种偷梁换柱的感觉.

FF算法

Ford_Fulkerson算法(FF算法)就是基于这两个做的,不停的利用反向弧寻找增广路,复杂度$O(F\times E)$,F为最大流的流量,因为最坏情况下每次最大流量增加1,每次dfs寻找增广路复杂度为$O(E)$.

Dinic算法

• 层次图: 就是从源点bfs,到节点u,距离为d[u],我们把d[u]叫做u的层次.
• 阻塞流:多次增广后,层次图中不存在由s->t的路径.

算法由bfs求层次图,dfs求增广路组成.

引入层次图是防止盲目搜索,只做一次dfs,就求出这次层次图的所有增广路.

复杂度为$O(V^2 \times E)$

dinic

参考:

江南的博客