网络流

 

网络流

很多问题都可以转化成网络流问题,如运输货物时的物流问题,水流问题,匹配问题等等。网络是一个各条边都有权值和方向的图。

网络流问题,一般情况下我们会把各种网络问题抽象成网络流问题,网络流是满足以下性质的网络:每一条边拥有一个最大的容量c,即该条边可以容纳的最大流量,f是流过该边的实际流量,且总有f<=c。对于图中每个顶点(源点和汇点除外)都有流出的流量等于流入的流量。图中只有一个源点一个汇点,且对于源点来说其流入量为0,对于汇点来说流出量为0,源点的流出量等于汇点的流入量,对于最大流问题既是要找出流入汇点的最大流量值。

求最大流的算法:

EK算法:EK算法中涉及的三个关键词:残留网络,增广路,割。

残留网络,假定我们已经找到了一个可行的流,那么对于每条边如果流量小于容量则表示该条边有剩余,以流的流量我们也可以看成是反向的残留,得到一个残留网络。

增广路:在残留网络中如果可以找到一条从源点到汇点的路,即为增广路,我们就可以将流值增加这条增广路上的最小边。

EK算法就是在残留网络中寻找增广路使得流值不断增大,直至达到最大为止。

Ek算法由于在寻找增广路时具有盲目性,算法效率不高。

 

Dinic算法:基于EK算法的思想,再从源点到汇点做bfs来寻找路时,对各点标一个层次值表示从源点到该点所需的最小步数,然后在这些层次的基础上做dfsdfs的时候只能到其下一层的点,且容量需要比已流流量大,然后重复上述过程即可得到解。

 

最大流和最小割,如果我们想要把一个网络分成两部分,一部分包含源点s,另一部分包含汇点t,我们把这个集合之间,从源集合到汇集合之间的正向流量之和,称为是网络的割,而一个网络的割中最小的那个,我们称之为最小割。

最大流最小割定理:一个网络的最小割等于最大流。

 

最小费用最大流:在保证最大流的情形下,网络中的边,可能不只有流量还有费用,那么如果我们一方面希望网络拥有最大流,另一方面我们要求费用达到最小,这就是一个费用流的问题了,对于费用流的问题,事实上我们可以这么考虑,首先我们必须要找到的是最大流,另一方面我们需要费用最小,而在找最大流的时候我们总是在寻找增广路来增广,来使得我们能得到一个比现在更大的流,那么另一方面要求费用最小,所以我们可以在寻找增广路的时候找一条费用最小路来增广,而费用我们也可以看成是距离类的东西,也就是这样的话,我们可以用最短路,来找出这样一个最小费用的路来进行增广,而不断增广,即可得到最大流,这样我们就可以得到最小费用最大流。

 

网络流和费用流中经常会涉及到拆点的操作,将一个点分成入和出,来拆成两个点。例如联合训练赛的第六场第一个题目tour,给出一张图,要求将这个图划分成几个集合,要求每个集合的点的个数大于等于2,要求这个集合所有点可以构成一个环。图中的每条边都有一个边权,最后找到各个集合的总花费为所有构成环的边的权之和。要求这个花费最小。分析题目可以知道,我们最后分成各个集合之后一定是每个点的出度和入度都为1,所以这个题经过拆点之后就是最小权匹配问题,用km算法即可解决,当然我们也可以将它转化成一费用流问题,将图中的每个节点都拆成入和出两个点,增加源和汇,源点到进入的点连一条费用为0,流量为1的边,从出点到汇连一条费用为0,流量为1的边,原图中的边都练成费用为边权,流量为1的边 ,最后只要求这个网络的最小费用流即可。另外对于一些题是点权而不是边权的题目,也可以通过拆点来将点权转化成边权。所以拆点的想法在网络流中十分重要。

 

posted on 2010-07-31 16:04 YUANZX 阅读(4411) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年7月>
27282930123
45678910
11121314151617
18192021222324
25262728293031
1234567

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜