搜索
1网络流问题入门多年来，考察网络流建模和算法的题目越来越多地出现在信息学竞赛中，网络流也已经被确定为信息学培训的重点章节。网络流问题里的构图是最考验做题人的思维的。题海不可取，总结是必须的。网络流的学习要在学习代码模板的基础上，深刻理解网络流模型的建立。1.1网络及网络流什么是网络？网络其实就是有向带权图。为什么要叫网络，是因为权值是容量，容量意味着可以在单位时间内经过的上限，但是可以比上限小。有向图=点集+有向边集一个实例：运输网络图1.1网络定义：一个有向图G=(V，E)；V代表点的集合，E代表边的集合。有两个特别的点：源点s、汇点t；图中每条边(u,v)∈E，有一个非负值的容量C(u,v)记为G=(V，E，C)网络三要素：点、边、容量可行流定义：是网络G上的一个“流”，即每条边上有个“流量”P(u,v)，要满足下面两个条件：流的容量限制---弧：),(),(0vuCvuP对任意弧(u,v)---有向边流的平衡---点：除源点和汇点，对任意中间点有：流入u的“流量”与流出u的“流量”相等。即：},{tsVu有VxVxxuPuxP0),(),(网络的流量：源点的净流出“流量”或汇点的净流入“流量”。即：D3SABCTE3214235VxVxVxVxxtPtxPsxPxsP),(),(),(),(注意，我们这里说的流量是一种速率，而不是指总量。联系上面所说的实例，下面是一个流量为1的可行流：图1.2标准图示法：图1.31.2、最大流问题寻找网络G上可能的最大流量(和一个有最大流量的可行流方案)，即为网络G上的最大流问题。我们再来看看图1.1的运输网络例子，我们可能通过改进图1.3得到下面这样的可行流：图2.1D3SABCTE3104234111D0/3SABCTE0/31/21/10/40/20/31/5D1/3SABCTE1/32/21/10/40/20/31/5求解过程中的困惑：[问题2.1]流量还可能增加吗？[问题2.2]如果能增加，怎样改进？1.3、最大流算法的核心---增广路径退流的概念---后向弧仔细分析图2.1，我们发现，流量是可以增加的：图3.1把一个流量弧(B,C)和(C,T)上的流退回到B点，改道从B-D-E-T走，就可以增加流量了，如下图：图3.2图3.1不能“直接寻找增大流的路径”，是因为当初有些弧上的流选择不“恰当”，要“退流”。一种直观的想法就是：调整或重新搜索“当初的选择”---难!能不能保留以前的工作，而在这之上改进呢？经过专家们研究发现，加入退流思想---后向弧，就能再次“直接寻找增大流的路径”。增广路径(可改进路径)的定义若P是网络中连结源点s和汇点t的一条路，我们定义路的方向是从s到t，则路上的弧有两种：前向弧---弧的方向与路的方向一致。前向弧的全体记为P+；后向弧---弧的方向与路的方向相反。后向弧的全体记为P-；设F是一个可行流，P是从s到t的一条路，若P满足下列条件：D1/3SABCTE1/31/21/11/41/21/30/5D2/3SABCTE2/32/21/11/41/21/31/5在P+的所有前向弧(u,v)上，0≦f(u,v)C(u,v);在P-的所有后向弧(u,v)上，0f(u,v)≦C(u,v);则称P是关于可行流F的一条可增广路径。图3.3本图中：S-A-C-B-D-E-T为一增广路径。其中(C,B)为后向弧，其它为前向弧。在增广路径上的改进算法：1)求路径可改进量；}u)f(v,),(),({min)(),(、后向弧前向弧vufvuCPCPvuf2)修改增广路径上的流量；1.4、附加网络1---残留网络由于要考虑前向弧、后向弧，分析、描述时不简洁，在图2.1上直观看也不容易看出增广路径。因此我们把已经有的流量从容量中分离出来表示，引入一个与原问题等价的附加网络1：残留网络。图4.1其中，前向弧(黑色)上的容量为“剩余容量”=C(u,v)-f(u,v)；后向弧(红色双线)上的容量为“可退流量”=f(v，u)。改造后的网如下：D1/3SABCTE1/32/21/10/40/20/31/5D2SABCTE200423411112图4.2在这张图上，我们找增广路径显的非常直观了!结合增广路径，我们有如下定理：最大流定理如果残留网络上找不到增广路径，则当前流为最大流；反之，如果当前流不为最大流，则一定有增广路径。证明涉及最小割概念，具体自己百度。至此，[问题2.1]和[问题2.2]在这个最大流定理中同时获得解决。求最大流的基本思想：基于这种思想的算法，关键之处在于怎样找增广路径。常用方法有：深度搜索dfs：Ford-Fulkerson算法，也是入门算法。宽度搜索bfs优先搜索pfs---即类似Dijkstra算法的标号法。1.5.最大流的代码实现下面我们来学习一下dfs求最大流的代码实现：【P1318】ditchD2SABCTE2423411112初始化一个可行流：Vvu,0),(对所有vuf现有网络流的残留网络上有增广路径吗？按上面方法对增广路径改进f为最大流YN在农夫约翰的农场上，每逢下雨，Bessie最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。【输入格式】第1行:两个用空格分开的整数N(0=N=200)和M(2=M=200)。N是农夫John已经挖好的排水沟的数量，M是排水沟交叉点的数量。交点1是水潭，交点M是小溪。第二行到第N+1行:每行有三个整数，Si,Ei,和Ci。Si和Ei(1=Si,Ei=M)指明排水沟两端的交点，雨水从Si流向Ei。Ci(0=Ci=10,000,000)是这条排水沟的最大容量。【输出格式】一个整数，即排水的最大流量。【分析】这道题就是一道最基本的网络流，只需要按照要求建立网络模型，求出最大值即可。最大流的最基础写法如下，具体细节看注释。usingnamespacestd;constintoo=1000000;intn,m,a[3000][3000],sum=0,forward;boolvis[3000],check=true;voidinit(){cinmn;memset(a,0,sizeof(a));for(inti=1;i=m;i++){intx,y,z;cinxyz;a[x][y]+=z;//这是图论里经常出现的吭，表示可能出现重边。}}voiddfs(intk,intl)//k是顶点的编号，l是最小的增广流量{vis[k]=true;//dfs必须有的标记if(k==n)//找到汇点，{check=true;//全局变量，标记存在增广路径sum+=l;forward=l;//流量可以扩充l。并记录下l，在回溯时进行流量操作。return;}for(inti=1;i=n;i++){if((a[k][i]0)&&(!vis[i]))//dfs固有的东西。{dfs(i,min(a[k][i],l));if(check)//这里是dfs后，回溯的位置{a[k][i]-=forward;//正向减去流量a[i][k]+=forward;//逆向（可退流边）加上这个流量return;}}}}intmain(){init();while(check)//只要还能找到可增广路，就一直找下去。{check=false;memset(vis,false,sizeof(vis));dfs(1,oo);}coutsumendl;return0;}通过以上代码，我们可以知道：1）邻接矩阵写网络流是最简单的，因为正向边和逆向边都存在邻接矩阵里。2）dfs的回溯来进行路径的增广，这样的写法是最简洁的。这个回溯用法和并查集的回溯用法是很经典的。我们本着一题多用的原则，思考一下，如何用邻接表来写这道题。如果要用邻接表写，需要注意几个问题：1）邻接矩阵的反向退流边还在邻接矩阵里，但是邻接表的退流边不是固定存在的，对于每条正向边，我们必须要新建一个和这条边对应的退流边。2）在建图的时候，先插入正向边，顺便再插入退流边，退流边的权值为0，并且给每条边再增加一个rev域，表示这条边的反向边的下标是多少，这样在流量减少的时候，顺便把反向边的流量增加上去。2关于网络流建图的相关例题【oj1319】N（3=N=200）头奶牛要办一个新年晚会。每头牛都会烧几道菜。一共有D(5=D=100)道不同的菜肴。每道菜都可以用一个1到D之间的数来表示。晚会的主办者希望能尽量多的菜肴被带到晚会，但是每道菜的数目又给出了限制。每头奶牛可以带K(1=K=5)道菜，但是必须是各不相同的（例如，一头牛不能带三块馅饼，但是可以带上一块馅饼，一份面包，和一些美味的桔子酱苜蓿）。那么，究竟有多少菜可以被带来晚会呢？例如：有4头奶牛，每头奶牛最多可以带3盘食品。一共有5种食品，它们的数量上限是2、2、2、2、3。奶牛1会做食品1…4，奶牛2会做食品2…5，奶牛3会做食品1、2、4，奶牛4会做食品1…3。那么最多可以带9盘食品到晚会上。即奶牛1做食品2…4，奶牛2做食品3…5，奶牛3做食品1、2，奶牛4做食品1。这样，4种食品各有2、2、2、2、1盘。【分析】我们尝试建立一个有向图，通过流量限制来构图，并用网络流来解决它。如上面的例子，我们尝试建立下面的图。边：S=奶牛,保证每头奶牛带的食品的最大量。边：食品=T,保证每种食品的最大数量。食品的总盘数最大值=S到T的最大流S到T的最大流=9.这道题需要好好理解一下，并思考网络流建图的规则，经验都是积累出来的。【oj1324】农夫JOHN为牛们做了很好的食品,但是牛吃饭很挑食.每一头牛只喜欢吃一些食品和饮料而别的一概不吃.虽然他不一定能把所有牛喂饱,他还是想让尽可能多的牛吃到他们喜欢的食品和饮料.农夫JOHN做了F(1=F=100)种食品并准备了D(1=D=100)种饮料.他的N(1=N=100)头牛都以决定了是否愿意吃某种食物和喝某种饮料.农夫JOHN想给每一头牛一种食品和一种饮料,使得尽可能多的牛得到喜欢的食物和饮料.每一件食物和饮料只能由一头牛来用.例如如果食物2被一头牛吃掉了,没有别的牛能吃食物2.【分析】由于有N只奶牛、F种食物和D种饮料，因此我们可以将这些东西抽象成图中的点。为了方便，我们将食物放在左边，奶牛放在中间，饮料放在右边。沿用前面的建模方式，由于食物和饮料的使用限制，我们从源点向每种食物连一条边，从每种饮料向汇点连一条边，容量都为1。而每只奶牛都有喜欢的食物和饮料，因此将每只奶牛喜欢的食物连到这只奶牛，从这只奶牛连到每种它喜欢的饮料。但这样是否就对了呢？实际还是有问题的，因为经过每只奶牛的食物可能超过一种，这就意味着每只奶牛可能会吃超过一组的食物和饮料，而这在题目中是不允许的。怎么解决这个问题呢？我们又回到了流的基本性质：容量限制f(u,v)c(u,v)。因此我们将每只奶牛拆成两个点，同一只奶牛的两个点之间连边，容量为1。这样我们就能保证通过每只奶牛的流量为1了。每个流对应每种方案，最大流即为最佳方案。可见最大流模型的一般建模思路是运用流的容量限制，使得题目中的约束得以满足，有时还需使用一些特殊的方法（如上题中的拆点）来满足题目的特别约束。【oj1609】尼克在一家养猪场工作，这家养猪场共有M间锁起来的猪舍，由于猪舍的钥匙都给了客户，所以尼克没