本文共 1428 字，大约阅读时间需要 4 分钟。

最近做题遇到了网络流方面的问题，正好蓝书（刘汝佳的《算法竞赛入门经典-训练指南》）上有介绍，大多数的ACMer应该都有买过他的书，话不多说，开始讲概念

容量网络:设G(V,E),是一个有向网络,在V中指定了一个顶点,称为源点(记为Vs),以及另一个顶点,称为汇点(记为Vt);对于每一条弧<u,v>属于E,对应有一个权值c(u,v)>0,称为弧的容量.通常吧这样的有向网络G称为容量网络.

弧的流量:通过容量网络G中每条弧<u,v>,上的实际流量(简称流量),记为f(u,v);

网络流:所有弧上流量的集合f={f(u,v)},称为该容量网络的一个网络流.

可行流:在容量网络G中满足以下条件的网络流f,称为可行流.

a.弧流量限制条件:   0<=f(u,v)<=c(u,v); b:平衡条件:即流入一个点的流量要等于流出这个点的流量,(源点和汇点除外).

若网络流上每条弧上的流量都为0,则该网络流称为零流.

伪流:如果一个网络流只满足弧流量限制条件,不满足平衡条件,则这种网络流为伪流,或称为容量可行流.(预流推进算法有用)

最大流:在容量网络中,满足弧流量限制条件,且满足平衡条件并且具有最大流量的可行流,称为网络最大流,简称最大流.

弧的类型:

a.饱和弧:即f(u,v)=c(u,v);

b.非饱和弧:即f(u,v)<c(u,v);

c.零流弧:即f(u,v)=0;

d.非零流弧:即f(u,v)>0.

设P是G中一条从Vs到Vt的链,约定从Vs指向Vt的方向为正方向.在链中并不要求所有的弧的方向都与链的方向相同.

a.前向弧:(方向与链的正方向一致的弧),其集合记为P+

b.后向弧:(方向与链的正方向相反的弧),其集合记为P-

那么如何求最大流呢。可以采用著名的Ford-Fulkerson（福特-福克森）算法，我们一般称为FF算法

步骤：

重点来了！什么是增广路径呢？这个概念很多人应该是不理解的，毕竟也是第一次听到。所谓增广路径，就是找到这样一条路径，其流量未满，未达到容量上限。我们想象成一个管道一样，管道里还有水流动，那就代表存在增广路径。

设某一增广路径上的节点为（a1,a2,a3,a4,…,an）

如果（u,v）是正向边，则增加流量d = min{ c(ai,aj) - f(ai,aj) | j = i +1, i =1,2,3…,n-1}

如果是逆向边，则增加流量d = min{ f(ai, aj) | j = i +1, i =1,2,3…,n-1}

第二步，更新流量

如果（u,v）是正向边，则 f(u,v) = f(u,v) + d

是逆向边，则f(u,v) = f(u,v) - d

注意，如果是逆向边，就是减法，当前管道从中减去部分流量，而且，伴随着这部分减去的流量，必有另一部分管道的流量会增加。。而且，最后的总流量增加了d

关于网络流的相关基础概念就介绍到这里了，下一篇博客是通过一个例题HDU 1532给出

转载地址：https://chocolate.blog.csdn.net/article/details/98475891 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！