网络流2013版

1、1网络流问题入门多年来，考察网络流建模和算法的题目越来越多地出现在信息学竞赛中，网络流也已经被确定为信息学培训的重点章节。网络流问题里的构图是最考验做题人的思维的。题海不可取，总结是必须的。网络流的学习要在学习代码模板的基础上，深刻理解网络流模型的建立。1.1网络及网络流什么是网络？网络其实就是有向带权图。为什么要叫网络，是因为权值是容量，容量意味着可以在单位时间内经过的上限，但是可以比上限小。有向图=点集+有向边集一个实例：运输网络D3SABCTE3214235图1.1网络定义：l 一个有向图 G=(V，E)； V代表点的集合，E代表边的集合。l 有两个特别的点：源点s、汇点t；l 图中每条

2、边(u,v)E，有一个非负值的容量C(u,v)记为 G=(V，E，C)网络三要素：点、边、容量可行流定义：是网络G上的一个“流”，即每条边上有个“流量”P(u,v)，要满足下面两个条件：流的容量限制-弧： 对任意弧(u,v)-有向边流的平衡-点： 除源点和汇点，对任意中间点有：流入u的“流量”与流出u的“流量”相等。即： 有 网络的流量：源点的净流出“流量” 或 汇点的净流入“流量”。即：D3SABCTE3104234111注意，我们这里说的流量是一种速率，而不是指总量。联系上面所说的实例，下面是一个流量为1的可行流：图1.2标准图示法：D0/3SABCTE0/31/21/10/40/20/3

3、1/5图1.31.2、最大流问题 寻找网络G上可能的最大流量(和一个有最大流量的可行流方案)，即为网络G上的最大流问题。 我们再来看看图1.1的运输网络例子，我们可能通过改进图1.3得到下面这样的可行流：D1/3SABCTE1/32/21/10/40/20/31/5图2.1 求解过程中的困惑：问题2.1流量还可能增加吗？问题2.2如果能增加，怎样改进？1.3、最大流算法的核心-增广路径退流的概念-后向弧仔细分析图2.1，我们发现，流量是可以增加的：D1/3SABCTE1/31/21/11/41/21/30/5图3.12/3把一个流量弧(B,C)和(C,T)上的流退回到B点，改道从B-D-E-T

4、走，就可以增加流量了，如下图：2/2CA1/52/3T1/31/1S1/4B1/2ED图3.2图3.1不能“直接寻找增大流的路径”，是因为当初有些弧上的流选择不“恰当”，要“退流”。一种直观的想法就是：调整或重新搜索“当初的选择”-难!能不能保留以前的工作，而在这之上改进呢？经过专家们研究发现，加入退流思想-后向弧，就能再次“直接寻找增大流的路径”。增广路径(可改进路径)的定义 若P是网络中连结源点s和汇点t的一条路，我们定义路的方向是从s到t，则路上的弧有两种：l 前向弧-弧的方向与路的方向一致。前向弧的全体记为P+；l 后向弧-弧的方向与路的方向相反。后向弧的全体记为P-； 设F是一个可行

5、流，P 是从s到t的一条路，若P满足下列条件：在P+的所有前向弧(u,v)上，0f(u,v) < C(u,v);在P-的所有后向弧(u,v)上，0<f(u,v) C(u,v); 则称P是关于可行流F的一条可增广路径。2/2C1/31/51/3ATS0/31/10/4B0/2ED图3.3本图中：S-A-C-B-D-E-T 为一增广路径。其中(C,B)为后向弧，其它为前向弧。在增广路径上的改进算法：1) 求路径可改进量；2) 修改增广路径上的流量；1.4、附加网络1-残留网络由于要考虑前向弧、后向弧，分析、描述时不简洁，在图2.1上直观看也不容易看出增广路径。 因此我们把已经有的流量从

6、容量中分离出来表示，引入一个与原问题等价的附加网络1：残留网络。0C2122A141TS30124BED图4.1 其中，前向弧(黑色)上的容量为“剩余容量”=C(u,v)-f(u,v)；后向弧(红色双线)上的容量为“可退流量”=f(v，u)。改造后的网如下：D2SABCTE2423411112 图4.2 在这张图上，我们找增广路径显的非常直观了!结合增广路径，我们有如下定理：最大流定理 如果残留网络上找不到增广路径，则当前流为最大流；反之，如果当前流不为最大流，则一定有增广路径。 证明涉及最小割概念，具体自己百度。 至此，问题2.1和问题2.2在这个最大流定理中同时获得解决。求最大流的基本思想

7、： 初始化一个可行流： 现有网络流的残留网络上有增广路径吗？按上面方法对增广路径改进f为最大流YN基于这种思想的算法，关键之处在于怎样找增广路径。常用方法有：l 深度搜索dfs ：Ford-Fulkerson 算法，也是入门算法。l 宽度搜索bfsl 优先搜索pfs-即类似Dijkstra算法的标号法。1.5.最大流的代码实现下面我们来学习一下dfs 求最大流的代码实现：【P1318】ditch在农夫约翰的农场上，每逢下雨，Bessie最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦

8、恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。 农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。 根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。【输入格式】第1行: 两个用空格分开的整数N (0 <= N <= 200) 和 M (2 <= M <= 200)。N是农夫John已经挖好的排水

9、沟的数量，M是排水沟交叉点的数量。交点1是水潭，交点M是小溪。 第二行到第N+1行: 每行有三个整数，Si, Ei, 和 Ci。Si 和 Ei (1 <= Si, Ei <= M) 指明排水沟两端的交点，雨水从Si 流向Ei。Ci (0 <= Ci <= 10,000,000)是这条排水沟的最大容量。【输出格式】一个整数，即排水的最大流量。【分析】这道题就是一道最基本的网络流，只需要按照要求建立网络模型，求出最大值即可。最大流的最基础写法如下，具体细节看注释。using namespace std;const int oo=1000000;int n,m,a300030

10、00,sum=0,forward; bool vis3000,check=true;void init()cin>>m>>n;memset(a,0,sizeof(a);for (int i=1;i<=m;i+)int x,y,z;cin>>x>>y>>z;axy+=z; /这是图论里经常出现的吭，表示可能出现重边。void dfs(int k,int l) /k是顶点的编号，l是最小的增广流量visk=true; /dfs必须有的标记if (k=n) /找到汇点，check=true; /全局变量，标记存在增广路径sum+=l;

11、 forward=l; /流量可以扩充l。并记录下l，在回溯时进行流量操作。return;for (int i=1;i<=n;i+)if (aki>0)&&(!visi) /dfs固有的东西。dfs(i,min(aki,l);if (check) /这里是dfs后，回溯的位置aki-=forward; /正向减去流量aik+=forward; /逆向（可退流边）加上这个流量return;int main() init(); while (check) /只要还能找到可增广路，就一直找下去。 check=false; memset(vis,false,sizeof(v

12、is); dfs(1,oo); cout<<sum<<endl; return 0; 通过以上代码，我们可以知道：1） 邻接矩阵写网络流是最简单的，因为正向边和逆向边都存在邻接矩阵里。2） dfs的回溯来进行路径的增广，这样的写法是最简洁的。这个回溯用法和并查集的回溯用法是很经典的。我们本着一题多用的原则，思考一下，如何用邻接表来写这道题。如果要用邻接表写，需要注意几个问题：1）邻接矩阵的反向退流边还在邻接矩阵里，但是邻接表的退流边不是固定存在的，对于每条正向边，我们必须要新建一个和这条边对应的退流边。2）在建图的时候，先插入正向边，顺便再插入退流边，退流边的权值为0，

13、并且给每条边再增加一个rev域，表示这条边的反向边的下标是多少，这样在流量减少的时候，顺便把反向边的流量增加上去。2 关于网络流建图的相关例题【oj1319】 N（3<=N<=200）头奶牛要办一个新年晚会。每头牛都会烧几道菜。一共有D(5<=D<=100)道不同的菜肴。每道菜都可以用一个1到D之间的数来表示。晚会的主办者希望能尽量多的菜肴被带到晚会，但是每道菜的数目又给出了限制。每头奶牛可以带K(1<=K<=5)道菜，但是必须是各不相同的（例如，一头牛不能带三块馅饼，但是可以带上一块馅饼，一份面包，和一些美味的桔子酱苜蓿）。那么，究竟有多少菜可以被带来晚会

14、呢？例如：有4头奶牛，每头奶牛最多可以带3盘食品。一共有5种食品，它们的数量上限是2、2、2、2、3。奶牛1会做食品14，奶牛2会做食品25，奶牛3会做食品1、2、4，奶牛4会做食品13。那么最多可以带9盘食品到晚会上。即奶牛1做食品24，奶牛2做食品35，奶牛3做食品1、2，奶牛4做食品1。这样，4种食品各有2、2、2、2、1盘。 【分析】我们尝试建立一个有向图，通过流量限制来构图，并用网络流来解决它。如上面的例子，我们尝试建立下面的图。边：S=>奶牛, 保证每头奶牛带的食品的最大量。边：食品=>T, 保证每种食品的最大数量。食品的总盘数最大值=S到T的最大流S到T的最大流=9.

15、这道题需要好好理解一下，并思考网络流建图的规则，经验都是积累出来的。【oj1324】农夫JOHN为牛们做了很好的食品,但是牛吃饭很挑食. 每一头牛只喜欢吃一些食品和饮料而别的一概不吃.虽然他不一定能把所有牛喂饱,他还是想让尽可能多的牛吃到他们喜欢的食品和饮料.农夫JOHN做了F (1 <= F <= 100) 种食品并准备了D (1 <= D <= 100) 种饮料. 他的N (1 <= N <= 100)头牛都以决定了是否愿意吃某种食物和喝某种饮料. 农夫JOHN想给每一头牛一种食品和一种饮料,使得尽可能多的牛得到喜欢的食物和饮料.每一件食物和饮料只能由一

16、头牛来用. 例如如果食物2被一头牛吃掉了,没有别的牛能吃食物2.【分析】由于有 N 只奶牛、F 种食物和 D 种饮料，因此我们可以将这些东西抽象成图 中的点。为了方便，我们将食物放在左边，奶牛放在中间，饮料放在右边。沿用前面的建模方式，由于食物和饮料的使用限制，我们从源点向每种食物连一条边， 从每种饮料向汇点连一条边，容量都为 1。而每只奶牛都有喜欢的食物和饮料， 因此将每只奶牛喜欢的食物连到这只奶牛，从这只奶牛连到每种它喜欢的饮料。但这样是否就对了呢？实际还是有问题的，因为经过每只奶牛的食物可能超 过一种，这就意味着每只奶牛可能会吃超过一组的食物和饮料，而这在题目中是 不允许的。怎 么 解

17、决 这 个 问 题 呢 ？ 我 们 又 回 到 了 流 的 基 本 性 质 ： 容 量 限 制f (u, v) £ c(u, v) 。因此我们将每只奶牛拆成两个点，同一只奶牛的两个点之间连 边，容量为 1。这样我们就能保证通过每只奶牛的流量为 1 了。每个流对应每种方案，最大流即为最佳方案。可见最大流模型的一般建模思路是运用流的容量限制，使得题目中的约束得以满足，有时还需使用一些特殊的方法（如上题中的拆点）来满足题目的特别约 束。【oj1609】尼克在一家养猪场工作，这家养猪场共有M间锁起来的猪舍，由于猪舍的钥匙都给了客户，所以尼克没有办法打开这些猪舍，客户们从早上开始一个接一个来购

18、买生猪，他们到达后首先用手中的钥匙打开他所能打开的全部猪舍，然后从中选取他要买的生猪，尼克可以在此期间将打开的猪舍中的猪调整到其它开着的猪舍中，每个猪舍能存放的猪的数量是没有任何限制的。买完猪后客户会将他打开的猪舍关上。好在尼克事先知道每位客户手中有哪些钥匙，要买多少猪，以及客户到来的先后次序。请你写一个程序，帮助尼克求出最多能卖出多少头生猪。【分析】网络流的建图是很难得，福建师大附中的江鹏在论文从一道题目的解法试谈网络流的构造与算法的引论中也有这样一句话： “网络流在具体问题中的应用，最具挑战性的部分是模型的构造。这没用现成的模式可以套用，需要对各种网络流的性质了如指掌（比如点有容量、容量有

19、上下限、多重边等等），并且归纳总结一些经验，发挥我们的创造性。”3 最小割3.1 一些相关概念1到底什么是割：原始点集为V，选出一些点集S使得sS，T=V-S，tT，则S到T的边为S到T割，记做S,T。2什么是最小割：图中所有的割中，边权值和最小的割为最小割！上图一个割的例子，边的数字代表边的容量，割的容量是2+2+1+6=113割的容量容量和流量计算的区别：割S,T的容量为(边(u,v)的容量和)，其中uS,T。也就是说割的容量不计算反向的边！而流量为正向的和反向的代数和。4. 怎样求割 求完最大流后，在残留网络中从source开始dfs，被染色的为S，未被染色的为T，则边集S,T为割。 5

20、最大流-最小割定理：最大流的值为最小割的容量！（反证法）通俗简明的讲：“最大流小于等于最小割”。这是“流理论”里最基础最重要的定理。整个“流”的理论系统都是在这个定理上建立起来的，必须特别重视。下面我们给出证明。证明 对任意一个中间点（即非S、也非T的点）vi，恒有： （1）当vi = S时有 （2）从（1）、（2）对iU求和得因为：V = UW，所以又因： 即 故有：所以即V(f) C(U,W)命题得证。这里得证明是为了加深对最小割的了解。建议在脑子很清楚的条件下研读。网络流、可改进路、割切都是基础的概念，应该扎实掌握。它们三者之间乍一看似乎风马牛不相干，其实内在联系是十分紧密的。3.2 最

21、小割入门例题【OJ1320】patrolFJ有个农场，其中有n块土地，由m条边连起来。FJ的养牛场在土地1，在土地n有个新开张的雪糕店。Bessie经常偷偷溜到雪糕店，当Bessie去的时候，FJ就要跟上她。但是Bessie很聪明，她在从雪糕店返回时不会经过去雪糕店时经过的农场，因此FJ总是抓不住Bessie。为了防止Bessie生病，FJ决定把一些诚实的狗放在一些土地(1和n除外)上，使Bessie无法在满足每块土地最多只经过一次的条件的情况下，从养牛场溜到雪糕店然后又溜回养牛场。求出FJ最少要放多少只狗。数据保证1和n间没有直接的连边。【分析】最小割求的是割边，而这里求的是割点，怎么办？这

22、里的条件是 Bessie无法在满足每块土地最多只经过一次的条件的情况下 是我们的突破口。根据1324的经验，我们把每一个点拆成两个点，入点和出点，且入点到出点的流量为1.这样求一个最大流，得到的就是最小割。思考几个问题：1） 其他边的流量是多少？2） 用邻接矩阵是否可行。【oj1341】被污染的牛奶 milk6你第一天接手三鹿牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批有三聚氰胺的牛奶。很不幸，你发现这件事的时候，有三聚氰胺的牛奶已经进入了送货网。这个送货网很大，而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。送货网由一些仓库和运输卡车组成，每辆卡

23、车都在各自固定的两个仓库之间单向运输牛奶。在追查这些有三聚氰胺的牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失。你的任务是，在保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。输入格式：第一行: 两个整数N(2<=N<=32)、M(0<=M<=1000), N表示仓库的数目，M表示运输卡车的数量。仓库1代 表发货工厂，仓库N代表有三聚氰胺的牛奶要发往的零售商。 第2.M+1行: 每行3个整数Si,Ei,Ci。其中Si,Ei表示这 辆卡车的出发仓库，目的仓库。Ci(0 <= C i

24、 <= 2,000,000) 表示让这辆卡车停止运输的损失。输出格式：第1行两个整数c、t,c表示最小的损失，T表示要停止的最少卡车数。接下来t 行表示你要停止哪几条线路。如果有多种方案使损失最小，输出停止的线路最少的方案。如果仍然还有相同的方案，请选择开始输入顺序最小的。【分析】本道题就是要求最小割，那么求出最大流就是最小割，但是还要输出最小割最少包含的边的个数和方案。关键是是求出最小割边集合最少包含边的个数，标程用了一种很不错的方法。因为总共只有1000条边，那么将每个边容量*1001+1作为新的容量（注意这里指每次读入的每个边），那么最大流mod 1001就是最小割去的边数。最大流

25、=值 div 1001。首先这对最大流求肯定没影响，其次，我们知道对以每一条增广路大小取决于最小的那个，这里的+1就派上了用场。 在同样可一减去2条边和减去一条边使其不连通时，减去两条边对应+2>+1所以，求最大流时会选择+1 ，同样，对于那些必须删的边多少个+1其实就等于删了多少条边。再按编号从小往大的顺序枚举每条边，判断去掉之后最大流减小值是否等于边权。是则输出。【练习题OJ1342】农夫约翰的奶牛们喜欢通过电邮保持联系，于是她们建立了一个奶牛电脑网络，以便互相交流。这些机器用如下的方式发送电邮：如果存在一个由c台电脑组成的序列a1,a2,.,a(c)，且a1与a2相连，a2与a3相

26、连，等等，那么电脑a1和a(c)就可以互发电邮。 很不幸，有时候奶牛会不小心踩到电脑上，农夫约翰的车也可能碾过电脑，这台倒霉的电脑就会坏掉。这意味着这台电脑不能再发送电邮了，于是与这台电脑相关的连接也就不可用了。 有两头奶牛就想：如果我们两个不能互发电邮，至少需要坏掉多少台电脑呢？请编写一个程序为她们计算这个最小值和与之对应的坏掉的电脑集合。 以如下网络为例： 1* / 3 - 2*这张图画的是有2条连接的3台电脑。我们想要在电脑1和2之间传送信息。电脑1与3、2与3直接连通。如果电脑3坏了，电脑1与2便不能互发信息了。3.3网络流关键割边 定义：关键割边就是增加某条边的容量,可以使得网络的最

27、大流增加。 算法描述：首先对这个网络图跑一遍dinic（最大流），得到残余网络。再分别从s和t对残余网络进行dfs。对于一条边(a,b)如果从s可以到达a并且从t可以到达b则该边为关键割边。注意，满流的边不一定是关键割边。具体反例见胡波涛论文第8页。3.4一些割的性质 1.割S,T，流量只能从S流向T，不能从T流向S！ （在最大流后找割dfs时其实就满足这个性质，假设T中一个点v流向S中的一个点u，那么u到v有负流量，则u到v的残留网络严格大于0。 ）2.最大流后，割边一定满流。减小某一割边后，网络流减小。 3.如下图，从s沿着残余流量dfs，得到点集S；同理沿着t反向dfs，得到点

28、集T；剩下的是M。分界线cut1和cut2是其中一割，边自然为割边。然而在M中还存有割边（一定存有！否则M就没用了！） 4. 退化一下：如下图所示，S和T有相邻部分边集E1，S和M重合边集相邻部分边集E2，M和T相邻边集部分E3，那么直接升高E1中某条边的容量，会使整体容量直接增高！反之：而如果增大S和M相邻的割边或者M和T相邻的割边，网络流不直接增大，因为M中还存有割边限制 。继续退化：如果M=空集，cut1和cut2重合（变为cut），则网络中割唯一。可以通过 if ( |S|+|T|=总点数) 来判断 3.5 最大权闭合图以下内容参考 胡伯涛 最小割模型在信息学竞赛中的应用，感谢他为我们

29、提供这么优秀的论文。 看不懂以上论文的同学，可以试试看一下以下内容，本文无大量的数学符号，方便阅读理解。 首先我们由一道题来引入，见 OJP1343 太空飞行计划问题 。 这道题中，实验依赖于仪器，而实验和仪器都有权值，且仪器为负，实验为正。 这里闭合图的概念就很好引出了。在一个图中，我们选取一些点构成集合，记为V，且集合中的出边(即集合中的点的向外连出的弧)，所指向的终点(弧头)也在V中，则我们称V为闭合图。最大权闭合图即在所有闭合图中，集合中点的权值之和最大的V，我们称V为最大权闭合图。 左图中闭合图有 5、2,5、4,5 2,4,5、3,4,5 1,2,3,4,5、1,2,4,5 最大权

30、闭合图为3,4,5。 针对本题而言，我们将实验与仪器间连一条有向边，实验为起点(弧尾)，仪器为终点(弧头)。则如果我们选择一个闭合图，那么这个闭合图中包含的实验所需要的仪器也最这个闭合图里。而最大权闭合图即为题目的解。 了解了最大权闭合图的概念，接下来我们就需要知道如何求最大权闭合图。 首先我们将其转化为一个网络(现在不要问为什么,接下来会证明用网络可以求解)。构造一个源点S，汇点T。我们将S与所有权值为正的点连一条容量为其权值的边，将所有权值为负的点与T连一条容量为其权值的绝对值的边，原来的边将其容量定为正无穷。 上图即被转化为如左图网络。 首先引入结论，最小割所产生的两个集合中，其源点S所

31、在集合(除去S)为最大权闭合图，接下来我们来说明一些结论。?证明:最小割为简单割。 引入一下简单割的概念：割集的每条边都与S或T关联。(请下面阅读时一定分清最小割与简单割，容易混淆) 那么为什么最小割是简单割呢？因为除S和T之外的点间的边的容量是正无穷，最小割的容量不可能为正无穷。所以，得证。?证明网络中的简单割与原图中闭合图存在一一对应的关系。(即所有闭合图都是简单割，简单割也必定是一个闭合图)。 证明闭合图是简单割：如果闭合图不是简单割(反证法)。那么说明有一条边是容量为正无穷的边，则说明闭合图中有一条出边的终点不在闭合图中，矛盾。 证明简单割是闭合图：因为简单割不含正无穷的边，所以不含有

32、连向另一个集合(除T)的点，所以其出边的终点都在简单割中，满足闭合图定义。得正。?证明最小割所产生的两个集合中，其源点S所在集合(除去S)为最大权闭合图。 首先我们记一个简单割的容量为C,且S所在集合为N，T所在集合为M。 则C=M中所有权值为正的点的权值(即S与M中点相连的边的容量)+N中所有权值为负的点权值的绝对值(即N中点与T中点相连边的容量)。记(C=x1+y1);(很好理解，不理解画一个图或想象一下就明白了)。 我们记N这个闭合图的权值和为W。 则W=N中权值为正的点的权值-N中权值为负的点的权值的绝对值。记(W=x2-y2); 则W+C=x1+y1+x2-y2。 因为明显y1=y2

33、，所以W+C=x1+x2; x1为M中所有权值为正的点的权值，x2为N中权值为正的点的权值。 所以x1+x2=所有权值为正的点的权值之和(记为TOT). 所以我们得到W+C=TOT.整理一下W=TOT-C. 到这里我们就得到了闭合图的权值与简单割的容量的关系。 因为TOT为定值，所以我们欲使W最大，即C最小，即此时这个简单割为最小割，此时闭合图为其源点S所在集合(除去S)。得正。 至此，我们就将最大权闭合图问题转化为了求最小割的问题。求最小割用最小割容量=最大流，即可将问题转化为求最大流的问题。最大权闭合图练习： P1344 P17334 dinic 算法dinic算法要比上面Ford-Ful

34、kerson算法效率要高一些。我们看下面的例子：我们知道，Ford-Fulkerson算法是每次找到一条增广路径，这个图中如果用Ford-Fulkerson算法，23这条边的退流将会做9999次，极大的影响算法的效率。而dinic算法确可以有效的解决这个问题。下面的讲解只讲解dinic的基本原理和实现，不太纠结于证明。假设有以下的这幅图：先bfs一遍（注意只遍历容量不为0的边），求出所有节点的层数，用level数组记录。 接着就做网络流，其基本原理就是：在现有的level基础上，只按照level递增顺序找增广路径，且有一点不同的是当找到一条s->t的路径的时候，不是直接结束，而

35、是从当前路径上最小层次的顶点（顶点，当前路径最大流量的边上的点，就是下图的红点或绿点K）再次寻找可行流（一定要将当前层次的可行流全部找完啊！）【下面的原理描述来自国家集训队论文】整个dfs过程分为2个操作。如果p的最后一个顶点为汇点，也就是说找到了增广路，那么对p增广，注意到增广后一定有一条或多条p中的边被删除了。这时，我们使增广路径后退至p中从源点可到达的最后一个顶点。如果p的最后一个顶点不为汇点，那么观察最后那个的顶点u 。若在层次图中存在从u连出的一条边，比如(u,v)，我们就将顶点v放入路径p中，继续dfs遍历；否则，点u对之后的dfs遍历就没有用了，我们将点u以及层次图中连到u的所有

36、边删除，并且在p中后退一个点。Dfs过程将会不断重复这2个操作，直到从源点连出的边全部被删除为止。整个dinic的过程就是不断地先bfs，再dfs，直到bfs不能得到汇点的层数为止。下面给出一个dfs的图例，图中，红边代表找到的增广路p中的边。具体代码实现如下，我用的题目是usaco ditch 加强版的数据。用这个算法，套用最大权闭合图，就可以A掉noi06年最大获利那道题。自我感觉，dinic用几遍后，代码实现应该没有问题。5 费用流最大流问题要求从源点S流出尽可能多的流量，流过一条或多条边，到达汇点T，且每条边上流过的流量不大于该边的流量限制，一个单位的流在某条边上产生的费用等于边的费用

37、。而最小费用最大流问题就是要求在流量达到最大的情况下，总费用最小。由最大流的相关知识可知，当且仅当不存在S到T的增广路时，图中的流达到最大。那么我们可以每次从S流出一个单位的流量到达T，使得这个单位流量所产生的费用最小。从“形”的角度观察这个问题，每个单位的流在当前网络中产生的最小费用，等价于当前网络中S到T的最小权值路径的权值，即S到T最短路的长度。因此，可以用SPFA求最短路，每次选择残留网络中最短的增广路进行增广，直到不存在增广路为止，可以证明找到的最大流的费用一定最小。分析这个算法的时间复杂度，如果增广次数是w，每次SPFA算法在残留网络G上的运行时间是SPFA(G)，那么总的时间复杂

38、度就是O(w×SPFA(G)。用流量控制连通，每次找费用最小的增广路径，这样得到的最大流肯定是费用最小的。这是我对费用流的理解。Noip2008 传纸条因为要找两条不相交的路径让费用最大，我们可以利用费用流的模板来完成。让起点的流量为2，这样就可以约束只找两条路径，把费用变成负的，这样将最大费用改为最小费用。因为有向边，不会有流量环，我们可以将spfa的迭代改为大于号也行。下面是费用流的模板，希望认真研读。费用流例子：Sdoi 2009 晨跑要求一个路口不能经过两次以上。那么就把每个点拆成两个分别放在A部和B部里面。对于每个输入的x,y,z连一条Ax，By，流量为1，费用为z的边。再

39、从每个Bi向Ai连一条流量为1，费用为0的边控制只能走一次。源即1，汇为n+n。SDOI2010星际竞速这是道图论题是肯定的，图都给你了那么问题在于如何建模问题要求访问每个点恰好一次（我一开始没看到这个条件）要求总时间最短，尝试把问题转化为一些经典图论问题比如最短路很可惜不行，那么自然想到网络流（组里面有句戏言叫“一切皆可网络流”，比如A+B）进一步分析发现单纯的网络流是不行的，需要用费用流访问每个点恰好一次，跟路径覆盖其实有点像把每个星球拆成两个点，u和u'我们对每条题目给定的边(u,v)，在网络流中加一条边(u,v')，流量为1，费用为时间然后第一次可以前往任何一个点，那么

40、从st向v'连一条边，流量为1，费用为定位时间从每个v'向ed连一条边，容量为1，费用为0，表示每个点的的入度为1，仅会访问一次从st向每个u连一条边，容量为1，费用为0，以便u通过(u,v')到达v'那么这个图的最小费用流就是答案ZJOI2010network 求平均费用这个有点无趣啊。人数给定了其实只要求出最少的总时间花费就行了、不用搞什么分数规划。 这题费用流的算法是很明显的啦、就是构图很巧妙 N辆车，M个工人。 把每个工人拆成N个点。记为Ai,j表示第i个工人修倒数第j辆车。每个车跟所有N*M个工人拆出的点连边。流

41、量为1，费用为timei,j*k。源和每辆车连边，N*M个点和汇连边，流量都为1，费用同为0。 为什么这么构图呢？ 考虑第i个工人，他修第j辆车只对后面要修的车有影响，而前面修过的车已经对当前没有影响了。而这个影响就是后面每个将要修理的车都多等待了time的时间。 其他边流量都为1是显然的，每辆车修一次，每个工人一个时段只能修理一辆车。 跑一遍费用流，出解、【阅读材料】网络流问题可以说是OI中最灵活的问题之一了，建模方法很多，但还是有一定规律的囧网络流建模主要分为两类：直接用最大流建模、用最大流最小割定理转化为最小割来建模。这里主要总结的是前一种。（1）

42、增广路思想：应用范围较小，但是确实有一些模型用增广路思想很容易解释，用流量平衡思想却很难解释（比如下面举的例子）。增广路思想可以概括为：原题的方案的得出可以很明显地分为一些阶段，每一阶段都会对一些变量（这些变量可能是实的也可能是虚设的）产生同样的效果值累加，而这些变量恰好有各自的限制，且互不关联。这刚好相当于网络中的一条从源点到汇点的一条增广路，对路上所有边的流量都会增加，且流量有各自限制（容量），且互不关联。并且，该模型满足下面（3）中的两条原则（可行性原则和最优性原则）。在比较多的时候，用增广路思想能够解释的模型往往是一个很明显的“物质路径”模型，某一种物质（可以是实的也可以是虚的）从源点

43、往汇点“走”，边上的流量代表物质经过的量。例1：NOIP2011观光公交首先，由于来出发地的时间已知且一定，所以“旅行时间总和最小”其实就是所有人下车的时间总和尽可能小，因此，先求出在不用任何加速器（初始）情况下，到达每一站的时间，设为Si，又设Mi为在第i站上车的来的最晚的人来的时间，则很显然可以得到初始的递推式：Si=maxSi-1, Mi-1+Di-1（初始的D值），边界S0=0。下面来看一下Di的减少是如何影响S值的。看下面这个例子：N=5i ： 0 1 2 3 4Di（初始）： 3 4 3 2 Mi ： 1 2 6 14 Si（初始）： 0 4 8 11 16现在将D0的值减小1之后

44、：i ： 0 1 2 3 4Di： 2 4 3 2 Mi： 1 2 6 14 Si： 0 3 7 10 16可以发现，D0值减小1之后，S1.3的值都减小了1，而S4的值不变。这是因为在D0减小1之前，对于1<=i<3均有Si>Mi，D0若减小1，显然S1会减小1，而由于S1>M1，S1=maxS1, M1，所以S1的值减小1会使得maxS1, M1减小1，从而S2的值减小1，然后由于初始的S2>M2，同样会使得S3减小1，而初始的S3<=M3，故S3减小1不会使得maxS3, M3发生变化，所以S4的值不会受到影响。所以，可以得到：Di减小1，会使得Si+

45、1.j+1均减小1，其中j是使任意i+1<=k<=j0均满足Sk（减小前）>Mk的最大的j0值。从这个当中可以发现，对于原题的每一个可行方案，必然都是分为若干个阶段，其中每一阶段是将某个Di值减小1（当然，要满足Di在减小前>0），每一阶段进行后都会将从Si+1开始的连续的一段S值都减小1，恰好可以抽象成一条连续的路径，又因为当Si减小到<=Mi的时候就必须停止了（准确来说是不能再往后延伸了），所以每个Si的能够继续延伸的减小的量都是有限的，为初始的Si-Mi（如果这个值<0，则取0），刚好是一个上限。这很明显是增广路思想。所以，经过整理，可以建立一个网络流

46、模型：<1>设立两个源点s和s'（其中s是真正的源点）及汇点t，连边<s, s'>，容量为K，费用为0，表示最多只能有K个阶段；<2>将每一站i拆成两个点i'和i''，连边<i', i''>，容量为max(Si-Mi, 0)，费用为0，表示该点最多只能接受max(Si-Mi, 0)次加速器作用；<3>对于所有的i满足1<=i<N，连边<(i-1)'', i'>，容量为INF，费用为第i站下车的人数（这是因为即使Si<=

47、Mi，加速器对于本站仍然有效，只是不能继续延伸，所以表示加速器起的效果的边应该在本站的限制之前）；<4>对于所有的i满足0<=i<N-1，连边<s', i''>，容量为初始Di，费用为0，表示使用加速器的地方，从下一站开始对Si起效果；<5>对于所有的i满足1<=i<N，连边<i', t>，容量为INF，费用为0，表示加速器作用的结束。（其实，0'和(N-1)''这两个点是木有任何意义的，可以从图中删掉）这样，每一阶段加速器的作用都可以表示为一条从s到t的增广路，该网

48、络流模型中的各种限制也反应了题目中的限制。对该网络求最大费用最大流，得到的总的最大费用从初始的总旅行时间中减去（注意总旅行时间是long long的），即为答案。可以证明，这个模型符合“两条原则”，所以是正确的。（2）流量平衡思想：这个思想的应用非常广，可以解释绝大多数网络流模型。所谓流量平衡，就是指在一个可行流里，除了源点和汇点外，其余每个点的入边流量总和都等于出边流量总和。可以证明，一个流是可行流当且仅当其：（1）每条边的流量都不超过容量限制；（2）符合流量平衡。流量平衡思想的主要用处是：可以把图中的每条边的流量（当然必须是非负的）都想像为一个变量的值，对于每个点，满足流量平衡，也就是一些

49、变量的和值满足某种等量关系，如果这些等量关系刚好能够反映题目中的所有信息，边的容量限制也反映题目中的条件，且这个模型符合“两条原则”，则该模型就是正确的了。在建模的时候，应先单独考虑各个点，找到它们的所有入边和出边代表的变量是什么，然后再将这些边合并，构成图。在用流量平衡建模时有一些技巧：<1>要注意每条边都同时作为一个点的出边和一个点的入边，因此，每个变量必然同时关联两个等量关系，且分别出现在这两个等量关系的等号的左边和右边（或者是以一对相反数形式出现）；<2>如果题目中给出的变量和值关系不是等量关系，而是不等关系，那么可以将剩余的流量通过从源点或往汇点连边的办法，使

50、其平衡。比如，若题目中有y1+y2>=x1+x2>=y1+y2-5这样的关系，则可以这样做：设置一个点，将y1、y2代表的边作为该点的入边，将x1、x2代表的边作为该点的出边，然后从该点往汇点连一条容量为5的边；<3>如果点内部有限制（比如某个点自身的权值不能超过X等等），那么该点内部也“暗含”一个变量，此时就需要拆点（不一定拆成两个点，可能拆成更多的点），然后在拆出的点当中再连边，附加一些限制，然后再考虑流量平衡；<4>如果一条边有上下界，且上下界相等（也就是该边的流量已经定死了），则可以改装成费用流，将这条边的费用设为一个绝对值很大的负数，这样就肯定能保证该边满流了。例2：餐巾计划问题（经典问题）这个的模型用增广路思想根本就不能解释。其实，可以用增广路思想建立一个模型，但是是错误的，可以用下面的“两条原则”检查出来。&