网络流2013版..docx

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

2、t；图中每条边 (u,v) E，有一个非负值的容量 C(u,v)记为 G=(V ， E， C)网络三要素：点、边、容量可行流定义：是网络 G 上的一个“流” ，即每条边上有个“流量”P(u,v)，要满足下面两个条件：流的容量限制 - 弧：0P(u, v)C (u, v) 对任意弧 (u,v)-有向边流的平衡 -点：除源点和汇点，对任意中间点有：流入 u 的“流量”与流出u 的“流量”相等 。即：uV s, t有P( x,u)P(u, x) 0x Vx V网络的流量 ：源点的净流出“流量”或 汇点的净流入“流量” 。即：P(s, x)P( x, s)P( x,t )P(t, x)x Vx Vx

3、Vx V注意， 我们这里说的流量是一种速率 ，而不是指总量。联系上面所说的实例，下面是一个流量为1 的可行流：3C13A411S0T431B2E图 1.2D标准图示法：0/3C1/20/3A1/5S1/1T0/40/3B0/2图 1.3DE1.2、最大流问题寻找网络 G 上可能的最大流量 (和一个有最大流量的可行流方案 ) ，即为网络 G 上的最大流问题。我们再来看看图1.1 的运输网络例子，我们可能通过改进图1.3 得到下面这样的可行流：1/3C2/21/3A 1/5S1/1T0/40/3B0/2DE图 2.1求解过程中的困惑：问题 2.1流量还可能增加吗？问题 2.2如果能增加，怎样改进？

4、1.3、最大流算法的核心-增广路径退流的概念 -后向弧仔细分析图2.1，我们发现，流量是可以增加的：1/3C1/21/3A0/5S1/1T1/41/3B1/2DE图 3.1把一个流量弧 (B,C)和 (C,T)上的流退回到 B 点，改道从 B-D-E-T 走，就可以增加流量了，如下图：2/3C2/22/3A 1/5S1/1T1/41/3图 3.2B1/2DE图 3.1 不能 “直接寻找增大流的路径”，是因为当初有些弧上的流选择不“恰当”，要“退流”。一种直观的想法就是：调整或重新搜索“当初的选择”-难 !能不能保留以前的工作，而在这之上改进呢？经过专家们研究发现，加入退流思想- 后向弧 ，就能

5、再次“直接寻找增大流的路径”。增广路径 (可改进路径 )的定义若 P 是网络中连结源点s 和汇点 t 的一条路，我们定义路的方向是从弧有两种：前向弧 -弧的方向与路的方向一致。前向弧的全体记为P+；后向弧 -弧的方向与路的方向相反。后向弧的全体记为P-；s 到t，则路上的设 F 是一个可行流，P 是从 s 到 t 的一条路，若P 满足下列条件：在 P+的所有前向弧 (u,v) 上， 0 f(u,v) C(u,v); 在 P-的所有后向弧 (u,v) 上， 0f(u,v) C(u,v);则称 P 是关于可行流 F 的一条可增广路径 。1/31/3A1/5S 1/1B0/4D图 3.3本图中： S

6、-A-C-B-D-E-T为一增广路径。其中在增广路径上的改进算法：1) 求路径可改进量；C f( P) min 前向弧 C (u, v)(u ,v) P2) 修改增广路径上的流量；C2/2T0/30/2E(C,B) 为后向弧，其它为前向弧。f (u, v) 、后向弧 f(v, u)1.4、附加网络1-残留网络由于要考虑前向弧、后向弧，分析、描述时不简洁，在图2.1 上直观看也不容易看出增广路径。因此我们把已经有的流量从容量中分离 出来表示，引入一个与原问题等价的附加网络1：残留网络 。2C02A12411TS0431B2DE图 4.1其中，前向弧 (黑色 )上的容量为“剩余容量” =C(u,v

7、)-f(u,v) ；后向弧 (红色双线 )上的容量为“可退流量” =f(v ， u)。改造后的网如下：2C2A1241S1T431B2DE图 4.2在这张图上，我们找增广路径显的非常直观了!结合增广路径，我们有如下定理：最大流定理如果残留网络上找不到增广路径，则当前流为最大流；反之，如果当前流不为最大流，则一定有增广路径。证明涉及 最小割 概念，具体自己百度。至此， 问题 2.1和问题 2.2在这个最大流定理中同时获得解决。求最大流的基本思想：初始化一个可行流：f (u, v)0 对所有 u,vV现有网络流的残留网络上有增广路径吗？YN按上面方法对增广路径改进f 为最大流基于这种思想的算法，关

8、键之处在于怎样找增广路径。常用方法有：深度搜索 dfs： Ford-Fulkerson算法，也是入门算法。宽度搜索 bfs优先搜索 pfs- 即类似 Dijkstra 算法的标号法。1.5.最大流的代码实现下面我们来学习一下dfs 求最大流的代码实现：【 P1318】ditch在农夫约翰的农场上，每逢下雨，Bessie 最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了， 并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师， 农夫约翰已经在每条排水沟的一端安上了控制器，这样他可

9、以控制流入排水沟的水流量。农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网） 。需要注意的是，有些时候从一处到另一处不只有一条排水沟。根据这些信息， 计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。【输入格式】第 1 行 : 两个用空格分开的整数N (0 = N = 200)和 M(2=M=200)。N 是农夫 John已经挖好的排水沟的数量，M 是排水沟交叉点的数量。交点1 是水潭，交点M 是小溪。第二行到第 N+1 行 : 每行有三个整数， Si, Ei, 和 Ci 。 Si

10、和 Ei (1 = Si, Ei = M)指明排水沟两端的交点，雨水从Si 流向 Ei 。Ci (0 = Ci mn;memset(a,0,sizeof(a);for (int i=1;ixyz;axy+=z;/ 这是图论里经常出现的吭，表示可能出现重边。void dfs(int k,int l) /k是顶点的编号，l 是最小的增广流量visk=true; /dfs必须有的标记if (k=n)/ 找到汇点，check=true; / 全局变量，标记存在增广路径sum+=l; forward=l;/流量可以扩充l。并记录下l ，在回溯时进行流量操作。return;for (int i=1;i0)

11、&(!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(vis);dfs(1,oo);coutsumendl;return 0;通过以上代码，我们可以知道：1） 邻接矩阵写网络流是最简单的，因为正向边和逆向边都存在邻接矩阵里。2） dfs 的回溯

12、来进行路径的增广，这样的写法是最简洁的。这个回溯用法和并查集的回溯用法是很经典的。我们本着一题多用的原则，思考一下，如何用邻接表来写这道题。如果要用邻接表写，需要注意几个问题：1）邻接矩阵的反向退流边还在邻接矩阵里，但是邻接表的退流边不是固定存在的，对于每条正向边，我们必须要新建一个和这条边对应的退流边。2）在建图的时候，先插入正向边，顺便再插入退流边，退流边的权值为0，并且给每条边再增加一个 rev 域，表示这条边的反向边的下标是多少，这样在流量减少的时候，顺便把反向边的流量增加上去。2 关于网络流建图的相关例题【 oj1319 】N（ 3=N=200 ）头奶牛要办一个新年晚会。每头牛都会烧

13、几道菜。 一共有 D(5=D=100)道不同的菜肴。每道菜都可以用一个1 到 D 之间的数来表示。晚会的主办者希望能尽量多的菜肴被带到晚会，但是每道菜的数目又给出了限制。每头奶牛可以带 K(1=K奶牛 , 保证每头奶牛带的食品的最大量。边：食品 =T, 保证每种食品的最大数量。食品的总盘数最大值=S 到 T 的最大流S 到 T 的最大流 =9.这道题需要好好理解一下，并思考网络流建图的规则，经验都是积累出来的。【 oj1324 】农夫 JOHN 为牛们做了很好的食品 ,但是牛吃饭很挑食 . 每一头牛只喜欢吃一些食品和饮料而别的一概不吃 .虽然他不一定能把所有牛喂饱 ,他还是想让尽可能多的牛吃到

14、他们喜欢的食品和饮料 .农夫 JOHN 做了 F (1 = F = 100)种食品并准备了D (1 = D = 100)种饮料 . 他的 N (1 =N = 100)头牛都以决定了是否愿意吃某种食物和喝某种饮料. 农夫 JOHN 想给每一头牛一种食品和一种饮料,使得尽可能多的牛得到喜欢的食物和饮料.每一件食物和饮料只能由一头牛来用. 例如如果食物2 被一头牛吃掉了,没有别的牛能吃食物 2.【分析】由于有 N只奶牛、F种食物和 D种饮料，因此我们可以将这些东西抽象成图中的点。为了方便，我们将食物放在左边， 奶牛放在中间， 饮料放在右边。 沿用前面的建模方式，由于食物和饮料的使用限制，我们从源点向

15、每种食物连一条边，从每种饮料向汇点连一条边，容量都为 1。而每只奶牛都有喜欢的食物和饮料，因此将每只奶牛喜欢的食物连到这只奶牛，从这只奶牛连到每种它喜欢的饮料。但这样是否就对了呢？实际还是有问题的， 因为经过每只奶牛的食物可能超 过一种，这就意味着每只奶牛可能会吃超过一组的食物和饮料， 而这在题目中是 不允许的。怎么解决这个问题呢？我们又回到了流的基本性质：容量限制f (u, v)c(u, v) 。因此我们将每只奶牛拆成两个点，同一只奶牛的两个点之间连 边，容量为 1。这样我们就能保证通过每只奶牛的流量为1了。每个流对应每种方案，最大流即为最佳方案。可见最大流模型的一般建模思路是运用流的容量限

16、制， 使得题目中的约束得以满足，有时还需使用一些特殊的方法 （如上题中的拆点） 来满足题目的特别约 束。【 oj1609 】尼克在一家养猪场工作，这家养猪场共有M 间锁起来的猪舍，由于猪舍的钥匙都给了客户，所以尼克没有办法打开这些猪舍，客户们从早上开始一个接一个来购买生猪，他们到达后首先用手中的钥匙打开他所能打开的全部猪舍，然后从中选取他要买的生猪，尼克可以在此期间将打开的猪舍中的猪调整到其它开着的猪舍中，每个猪舍能存放的猪的数量是没有任何限制的。买完猪后客户会将他打开的猪舍关上。好在尼克事先知道每位客户手中有哪些钥匙， 要买多少猪， 以及客户到来的先后次序。 请你写一个程序，帮助尼克求出最多

17、能卖出多少头生猪。【分析】网络流的建图是很难得， 福建师大附中的江鹏在论文 从一道题目的解法试谈网络流的构造与算法的引论中也有这样一句话：“网络流在具体问题中的应用，最具挑战性的部分是模型的构造。这没用现成的模式可以套用， 需要对各种网络流的性质了如指掌并且归纳总结一些经验，发挥我们的创造性。（比如点有容量、容量有上下限 、多重边等等），”3 最小割3.1 一些相关概念1到底什么是割：原始点集为 V ，选出一些点集 S 使得 s S， T=V-S ， t T ，则 S 到 T 的边为 S 到 T 割，记做 S,T 。2什么是最小割：图中所有的割中，边权值和最小的割为最小割！上图一个割的例子，边

18、的数字代表边的容量，割的容量是2+2+1+6=113割的容量容量和流量计算的区别：割S,T 的容量为 (边 (u,v) 的容量和 )，其中 u S,T 。也就是说割的容量不计算反向的边！而流量为正向的和反向的代数和。4. 怎样求割求完最大流后，在残留网络中从source 开始 dfs，被染色的为S，未被染色的为T ，则边集S,T 为割。5最大流 -最小割定理：最大流的值为最小割的容量！（反证法）通俗简明的讲： “最大流小于等于最小割” 。这是“流理论”里最基础最重要的定理。整个“流”的理论系统都是在这个定理上建立起来的，必须特别重视。下面我们给出证明。证明对任意一个中间点（即非S、也非T 的点

19、） vi ，恒有：f ijf ji0（1）j Vj V当 vi = S 时有f Sj V ( f )（ 2）j V从（ 1）、（2）对 i U 求和得( f ijf ji )V ( f )i U , j V因为： V = U W，所以( f ijfji)( f ijfji)( f ijfji)V ( f )iU , jViU , jUiU , jW又因：f ijfji即( f ijf ji)0iU , jUi U , jUiU , jU故有：( f ijfji)V ( f )i U , jW所以V ( f )( f ijfji)fijcijC(U ,W)i U , j Wi U , j Wi

20、U , j W即 V(f) C(U,W)命题得证。这里得证明是为了加深对最小割的了解。建议在脑子很清楚的条件下研读。网络流、可改进路、 割切都是基础的概念，应该扎实掌握。它们三者之间乍一看似乎风马牛不相干，其实内在联系是十分紧密的。3.2 最小割入门例题【 OJ1320】 patrolFJ 有个农场，其中有 n 块土地，由 m 条边连起来。 FJ 的养牛场在土地 1，在土地 n 有个新开张的雪糕店。 Bessie 经常偷偷溜到雪糕店， 当 Bessie 去的时候， FJ 就要跟上她。 但是 Bessie很聪明， 她在从雪糕店返回时不会经过去雪糕店时经过的农场，因此 FJ 总是抓不住Bessie

21、。为了防止 Bessie 生病， FJ 决定把一些诚实的狗放在一些土地(1 和 n 除外 )上，使 Bessie 无法在满足每块土地最多只经过一次的条件的情况下，从养牛场溜到雪糕店然后又溜回养牛场。求出 FJ 最少要放多少只狗。数据保证1 和 n 间没有直接的连边。【分析】最小割求的是割边，而这里求的是割点，怎么办？这里的条件是Bessie 无法在满足每块土地最多只经过一次的条件的情况下是我们的突破口。根据 1324 的经验，我们把每一个点拆成两个点，入点和出点，且入点到出点的流量为1.这样求一个最大流，得到的就是最小割。思考几个问题：1） 其他边的流量是多少？2） 用邻接矩阵是否可行。【oj

22、1341 】被污染的牛奶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 +1所以，求最大流时会选择 +1 ，同样，对于那些必须删的边多少个+1 其实就等于删了多少条边。再按编号从小往大的顺序枚举每条边，判断去掉之后最大流减小值是否等于边权。是则输出。【练习题 OJ1342】农夫约翰的奶牛们喜欢通过电邮保持联系，于是她们建立了一个奶牛电

24、脑网络，以便互相交流。这些机器用如下的方式发送电邮：如果存在一个由c 台电脑组成的序列a1,a2,.,a(c)，且 a1 与 a2 相连， a2 与 a3 相连，等等，那么电脑a1 和 a(c)就可以互发电邮。很不幸， 有时候奶牛会不小心踩到电脑上，农夫约翰的车也可能碾过电脑，这台倒霉的电脑就会坏掉。这意味着这台电脑不能再发送电邮了，于是与这台电脑相关的连接也就不可用了。有两头奶牛就想： 如果我们两个不能互发电邮，至少需要坏掉多少台电脑呢？请编写一个程序为她们计算这个最小值和与之对应的坏掉的电脑集合。以如下网络为例：1*/3-2*这张图画的是有2 条连接的3 台电脑。我们想要在电脑1 和 2

25、之间传送信息。电脑1与3、2 与3 直接连通。如果电脑3 坏了，电脑1 与2 便不能互发信息了。3.3 网络流关键割边定义：关键割边就是增加某条边的容量,可以使得网络的最大流增加。算法描述：首先对这个网络图跑一遍dinic （最大流），得到残余网络。再分别从s 和 t 对残余网络进行dfs。对于一条边 (a,b)如果从 s 可以到达 a 并且从 t 可以到达b 则该边为关键割边。注意，满流的边不一定是关键割边。具体反例见胡波涛论文第8 页。3.4 一些割的性质1.割 S,T ，流量只能从S 流向 T ，不能从 T 流向 S！ （在最大流后找割dfs个性质， 假设 T 中一个点v 流向 S 中的

26、一个点u，那么 u 到 v 有负流量， 则络严格大于0。 ）时其实就满足这 u 到 v 的残留网2.最大流后，割边一定满流。减小某一割边后，网络流减小。3.如下图，从s 沿着残余流量dfs，得到点集S；同理沿着t 反向dfs，得到点集T；剩下的是M 。分界线 cut1 和 cut2 是其中一割，边自然为割边。然而在否则 M 就没用了！）M中还存有割边（一定存有！4.退化一下： 如下图所示， S 和 T 有相邻部分边集E1，S 和 M 重合边集相邻部分边集M 和 T 相邻边集部分E3，那么直接升高E1 中某条边的容量，会使整体容量直接增高！反之：而如果增大S 和 M 相邻的割边或者M 和 T 相

27、邻的割边，网络流不直接增大，因为中还存有割边限制。E2，M继续退化：如果 ( |S|+|T|=总点数M= 空集，) 来判断cut1和cut2重合（变为cut ），则网络中割唯一。可以通过if3.5 最大权闭合图以下内容参考胡伯涛最小割模型在信息学竞赛中的应用，感谢他为我们提供这么优秀的论文。看不懂以上论文的同学，可以试试看一下以下内容，本文无大量的数学符号，方便阅读理解。首先我们由一道题来引入，见OJP1343 太空飞行计划问题。这道题中，实验依赖于仪器，而实验和仪器都有权值，且仪器为负，实验为正。这里闭合图的概念就很好引出了。在一个图中，我们选取一些点构成集合，记为V，且集合中的出边 (即集

28、合中的点的向外连出的弧)，所指向的终点 (弧头 )也在 V 中，则我们称 V 为闭合图。最大权闭合图即在所有闭合图中，集合中点的权值之和最大的V ，我们称V 为最大权闭合图。左图中闭合图有5 、 2,5 、4,52,4,5 、3,4,51,2,3,4,5 、 1,2,4,5最大权闭合图为3,4,5 。针对本题而言，我们将实验与仪器间连一条有向边，实验为起点(弧尾 )，仪器为终点 (弧头 )。则如果我们选择一个闭合图，那么这个闭合图中包含的实验所需要的仪器也最这个闭合图里。而最大权闭合图即为题目的解。了解了最大权闭合图的概念，接下来我们就需要知道如何求最大权闭合图。首先我们将其转化为一个网络 (

29、现在不要问为什么 ,接下来会证明用网络可以求解 )。构造一个源点 S，汇点 T。我们将 S 与所有权值为正的点连一条容量为其权值的边，将所有权值为负的点与 T 连一条容量为其权值的绝对值的边，原来的边将其容量定为正无穷。上图即被转化为如左图网络。首先引入结论，最小割所产生的两个集合中，其源点S 所在集合(除去S)为最大权闭合图，接下来我们来说明一些结论。?证明 :最小割为简单割。引入一下简单割的概念：割集的每条边都与最小割与简单割，容易混淆)S 或T 关联。(请下面阅读时一定分清那么为什么最小割是简单割呢？因为除S 和T 之外的点间的边的容量是正无穷，最小割的容量不可能为正无穷。所以，得证。?

30、证明网络中的简单割与原图中闭合图存在一一对应的关系。单割也必定是一个闭合图)。(即所有闭合图都是简单割，简证明闭合图是简单割：如果闭合图不是简单割(反证法 )。那么说明有一条边是容量为正无穷的边，则说明闭合图中有一条出边的终点不在闭合图中，矛盾。证明简单割是闭合图：因为简单割不含正无穷的边，所以不含有连向另一个集合(除T)的点，所以其出边的终点都在简单割中，满足闭合图定义。得正。?证明最小割所产生的两个集合中，其源点S 所在集合 (除去 S)为最大权闭合图。首先我们记一个简单割的容量为C,且 S 所在集合为N， T 所在集合为M 。则 C=M 中所有权值为正的点的权值(即 S 与 M 中点相连

31、的边的容量)+N 中所有权值为负的点权值的绝对值(即 N 中点与T 中点相连边的容量)。记 (C=x1+y1);( 很好理解，不理解画一个图或想象一下就明白了)。我们记 N 这个闭合图的权值和为W 。则 W=N 中权值为正的点的权值-N 中权值为负的点的权值的绝对值。记 (W=x2-y2);则 W+C=x1+y1+x2-y2 。因为明显y1=y2 ，所以 W+C=x1+x2;x1 为 M 中所有权值为正的点的权值，x2 为 N 中权值为正的点的权值。所以 x1+x2= 所有权值为正的点的权值之和(记为 TOT).所以我们得到W+C=TOT. 整理一下 W=TOT-C.到这里我们就得到了闭合图的

32、权值与简单割的容量的关系。因为 TOT 为定值，所以我们欲使W 最大，即 C 最小，即此时这个简单割为最小割，此时闭合图为其源点S 所在集合 (除去 S)。得正。至此，我们就将最大权闭合图问题转化为了求最小割的问题。求最小割用最小割容量=最大流，即可将问题转化为求最大流的问题。最大权闭合图练习：P1344P17334 dinic算法dinic 算法要比上面Ford-Fulkerson 算法效率要高一些。我们看下面的例子：我们知道， Ford-Fulkerson 算法是每次找到一条增广路径，这个图中如果用 Ford-Fulkerson 算法， 2 3 这条边的退流将会做 9999 次，极大的影响

33、算法的效率。而 dinic 算法确可以有效的解决这个问题。下面的讲解只讲解dinic 的基本原理和实现，不太纠结于证明。假设有以下的这幅图：先 bfs 一遍（注意只遍历容量不为 0 的边），求出所有节点的层数，用 level 数组记录。接着就做网络流，其基本原理就是：在现有的level基础上，只按照level递增顺序找增广路径，且有一点不同的是当找到一条s-t 的路径的时候，不是直接结束，而是从当前路径上最小层次的顶点（顶点， 当前路径最大流量的边上的点，就是下图的红点或绿点K）再次寻找可行流（一定要将当前层次的可行流全部找完啊！）【下面的原理描述来自国家集训队论文】整个 dfs 过程分为2

34、个操作。如果p 的最后一个顶点为汇点，也就是说找到了增广路，那么对 p 增广，注意到增广后一定有一条或多条p 中的边被删除了。这时，我们使增广路径后退至 p 中从源点可到达的最后一个顶点。如果 p 的最后一个顶点不为汇点，那么观察最后那个的顶点u 。若在层次图中存在从u 连出的一条边，比如(u,v) ，我们就将顶点v 放入路径p 中，继续dfs 遍历；否则，点u 对之后的 dfs 遍历就没有用了，我们将点u 以及层次图中连到u 的所有边删除，并且在p 中后退一个点。Dfs 过程将会不断重复这2 个操作，直到从源点连出的边全部被删除为止。整个 dinic的过程就是不断地先bfs，再 dfs，直到

35、 bfs 不能得到汇点的层数为止。下面给出一个 dfs 的图例，图中，红边代表找到的增广路p 中的边。具体代码实现如下，我用的题目是usaco ditch 加强版的数据。用这个算法，套用最大权闭合图，就可以A 掉 noi06 年最大获利那道题。自我感觉， dinic 用几遍后，代码实现应该没有问题。5 费用流最大流问题要求从源点 S 流出尽可能多的流量， 流过一条或多条边， 到达汇点 T，且每条边上流过的流量不大于该边的流量限制， 一个单位的流在某条边上产生的费用等于边的费用。而最小费用最大流问题就是要求在流量达到最大的情况下，总费用最小。由最大流的相关知识可知，当且仅当不存在 S 到 T 的

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

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

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