网络流

可以依照这个来理解代码:

Dinic算法的大致步骤

1、建立网络(包括正向弧和反向弧(初始边权为0)),将总流量置为0

 

2、构造层次网络(怎么又有新概念 T_T)

简单的说,就是求出每个点u的层次,u的层次是从源点到该点的最短路径(注意:这个最短路是指弧的权都为1的情况下的最短路),若与源点不连通,层次置为-1

一遍BFS轻松解决

 

3、判断汇点的层次是否为-1

是:再见,算法结束,输出当前的总流量

否:下一步

 

4、用一次DFS完成所有增广,增广是什么呢?

增广(我的理解):通过DFS找上述的增广路,找到了之后,将每条边的权都减去该增广路中拥有最小流量的边的流量,将每条边的反向边的权增加这个值,同时将总流量加上这个值

DFS直到找不到一条可行的从原点到汇点的路

 

 5、goto 步骤2


下面我们来考虑如何求最大流。(含太强了现在的智能搜索,还含有增广路的认识

    首先,假如所有边上的流量都没有超过容量(不大于容量),那么就把这一组流量,或者说,这个流,称为一个可行流。一个最简单的例子就是,零流,即所有的流量都是0的流。

我们就从这个零流开始考虑,假如有这么一条路,这条路从源点开始一直一段一段的连到了汇点,并且,这条路上的每一段都满足流量<容量,注意,是严格的<,而不是<=。那么,我们一定能找到这条路上的每一段的(容量-流量)的值当中的最小值delta。我们把这条路上每一段的流量都加上这个delta,一定可以保证这个流依然是可行流,这是显然的。

    这样我们就得到了一个更大的流,他的流量是之前的流量+delta,而这条路就叫做增广路。

    我们不断地从起点开始寻找增广路,每次都对其进行增广,直到源点和汇点不连通,也就是找不到增广路为止。当找不到增广路的时候,当前的流量就是最大流,这个结论非常重要。

寻找增广路的时候我们可以简单的从源点开始做bfs,并不断修改这条路上的delta量,直到找到源点或者找不到增广路。

这里要先补充一点,在程序实现的时候,我们通常只是用一个c数组来记录容量,而不记录流量,当流量+1的时候,我们可以通过容量-1来实现,以方便程序的实现。


(你要具体看他这个程序是怎么实现的,每一次递归回来是在哪儿,我们实际上返回的最终是更改的delta,递归回来的也是) 

https://www.cnblogs.com/dchipnau/archive/2011/09/16/4985966.html大佬博客了解一下

原文地址:https://www.cnblogs.com/lkx422/p/10736959.html