网络流2013版讲解

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

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

3、V注意， 我们这里说的流量是一种 速率 ，而不是指总量。联系上面所说的实例，下面是 个流量为 1 的可行流：标准图示法：1.2、最大流问题寻找网络 G 上可能的最大流量 (和一个有最大流量的可行流方案 ) ，即为网络 G 上的最大 流问题。我们再来看看图 1.1 的运输网络例子，我们可能通过改进图 1.3 得到下面这样的可行流：图 2.1求解过程中的困惑：问题 2.1流量还可能增加吗？问题 2.2如果能增加，怎样改进？1.3、最大流算法的核心 -增广路径退流的概念 -后向弧仔细分析图 2.1，我们发现，流量是可以增加的：2/32/2图 3.22/31/11/把一个流量弧 (B,C)和(C,T)

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

5、全体记为P-；设 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 的一条可增广路径 。本图中： S-A-C-B-D-E-T 为一增广路径。其中 (C,B) 为后向弧，其它为前向弧。 在增广路径上的改进算法 ：1) 求路径可改进量；Cf (P) min 前向弧 C(u,v) f (u,v)、后向弧 f(v, u)(u,v) P2) 修改增广路径上的流量；1.4、附加网络 1-残留网络由于要考虑前向弧、后向

6、弧，分析、描述时不简洁，在图2.1 上直观看也不容易看出增广路径。因此我们把已经有的流量从容量中 分离 出来表示，引入一个与原问题等价的 附加网络 1： 残留网络 。图 4.1其中，前向弧 (黑色 )上的容量为“剩余容量” =C(u,v)-f(u,v) ；后向弧 (红色双线 )上的容量 为“可退流量” =f(v ，u)。改造后的网如下 ：图 4.2在这张图上，我们找增广路径显的非常直观了结合增广路径，我们有如下定理： 最大流定理 如果残留网络上找不到增广路径，则当前流为最大流；反之，如果当前流不为最大流， 则一定有增广路径。证明涉及 最小割 概念，具体自己百度。至此， 问题 2.1和问题 2.

7、2在这个最大流定理中同时获得解决。求最大流的基本思想：初始化一个可行流：f (u,v) 0对所有 u,v V基于这种思想的算法，关键之处在于怎样找增广路径。常用方法有： 深度搜索 dfs ： Ford-Fulkerson 算法，也是入门算法。 宽度搜索 bfs优先搜索 pfs- 即类似 Dijkstra 算法的标号法。1.5.最大流的代码实现面我们来学习一下 dfs 求最大流的代码实现：P1318】ditch在农夫约翰的农场上，每逢下雨， Bessie 最喜欢的三叶草地就积聚了一潭水。这意味着草地 被水淹没了， 并且小草要继续生长还要花相当长一段时间。因此， 农夫约翰修建了一套排水系统来使贝茜

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

9、John 已经挖好的排水沟的数量， M 是排水沟交叉点的数量。交点 1 是水潭，交点 M 是小溪。 第二行到第 N+1 行: 每行有三个整数， Si, Ei, 和 Ci。Si 和 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) / 找到汇点，

10、check=true; / 全局变量，标记存在增广路径sum+=l; forward=l; /流量可以扩充 l。并记录下 l ，在回溯时进行流量操作。return;for (int i=1;i0)&(!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

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

12、边再增加一个 rev 域，表示这条边的反向边的下标是多少，这样在流量减少的时候，顺便把反 向边的流量增加上去。2 关于网络流建图的相关例题【oj1319 】N(3=N=200 )头奶牛要办一个新年晚会。 每头牛都会烧几道菜。 一共有 D(5=D=100) 道不同的菜肴。每道菜都可以用一个 1到D 之间的数来表示。 晚会的主办者希望能尽量多的菜肴被带到晚会， 但是每道菜的数目又给出了限制。 每头奶牛 可以带 K(1=K奶牛, 保证每头奶牛带的食品的最大量。 边：食品 =T, 保证每种食品的最大数量。 食品的总盘数最大值 =S到 T的最大流S 到 T 的最大流 =9.这道题需要好好理解一下，并思考

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

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

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

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

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

18、小割的容量！ （反证法）通俗简明的讲： “最大流小于等于最小割” 。这是“流理论”里最基础最重要的定理。整 个“流”的理论系统都是在这个定理上建立起来的，必须特别重视。下面我们给出证明。证明 对任意一个中间点（即非S、也非 T 的点） vi ，恒有：fij fj V j V当 vi = S 时有ji1)fSj V(f ) jV2)从( 1)、(2)对i U 求和得(fij i U, j Vfji) V( f)因为：V = U W ，所以(fij i U ,j Vf ji ) (f ij i U ,j Uf ji )(fij i U ,j Wf ji )V(f)又因：fij i U ,j Ufj

19、ii U , j U(fij i U ,j Ufji)故有：(fij i U ,j Wf ji) V(f )C(U,W)所以V(f)(fijfji )fijciji U, j W i U,j W i U,j W即 V(f) C(U,W) 命题得证。这里得证明是为了加深对最小割的了解。建议在脑子很清楚的条件下研读。网络流、可改进路、 割切都是基础的概念，应该扎实掌握。它们三者之间乍一看似乎风马牛 不相干，其实内在联系是十分紧密的。3.2 最小割入门例题【OJ1320】patrolFJ有个农场，其中有 n 块土地，由 m条边连起来。 FJ的养牛场在土地 1，在土地 n 有个新 开张的雪糕店。 Be

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

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

22、氰胺的牛奶的时候， 有必要保证它不被送到零售商手里， 所以 必须使某些运输卡车停止运输， 但是停止每辆卡车都会有一定的经济损失。 你的任务是， 在 保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。输入格式：第一行 : 两个整数 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 ，

23、同样，对于那些必须删的边多少个 +1 其实就等于删了多少条边。 再按编号从小往大的顺序枚举每条边， 判断去掉之后最大流减小值是否等于边权。 是则输出。【练习题 OJ1342 】农夫约翰的奶牛们喜欢通过电邮保持联系， 于是她们建立了一个奶牛电脑网络， 以便互相交 流。这些机器用如下的方式发送电邮：如果存在一个由 c 台电脑组成的序列 a1,a2,.,a(c)， 且 a1 与 a2 相连， a2 与 a3 相连，等等，那么电脑 a1 和 a(c) 就可以互发电邮。很不幸， 有时候奶牛会不小心踩到电脑上， 农夫约翰的车也可能碾过电脑， 这台倒霉的电脑 就会坏掉。这意味着这台电脑不能再发送电邮了， 于

24、是与这台电脑相关的连接也就不可用了。 有两头奶牛就想： 如果我们两个不能互发电邮， 至少需要坏掉多少台电脑呢？请编写一个程 序为她们计算这个最小值和与之对应的坏掉的电脑集合。以如下网络为例：1*/3 - 2*这张图画的是有 2 条连接的 3 台电脑。我们想要在电脑 1 和 2 之间传送信息。电脑 1 与 3、 2与 3直接连通。如果电脑 3坏了，电脑 1与 2便不能互发信息了。3.3 网络流关键割边 定义：关键割边就是增加某条边的容量 ,可以使得网络的最大流增加。 算法描述：首先对这个网络图跑一遍dinic(最大流)，得到残余网络。再分别从 s和 t 对残余网络进行 dfs。对于一条边 (a,

25、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，得到点集 T；剩下的是 M。分界线 cut1和 cut2是其中一割，边自然为

26、割边。然而在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 最大权闭合图以下内容参考 胡伯涛 优秀的论文。最小割模型在信息学竞

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

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

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

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

31、的点的权值 -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.到这里我们就得到了闭合图的权值与简单割的容量的关系。因为 TOT 为定值， 所以我们欲使 W 最大，即 C 最小，即此时这个简单割为最小割， 此时闭合图为其源点 S 所在集合 （除去 S）。得正。至此，我们就将最大权闭合图问题转化为了求

32、最小割的问题。求最小割用最小割容量= 最大流，即可将问题转化为求最大流的问题。最大权闭合图练习： P1344 P17334 dinic 算法dinic 算法要比上面 Ford-Fulkerson 算法效率要高一些。我们看下面的例子：我们知道， Ford-Fulkerson 算法是每次找到一条增广路径，这个图中如果用 Ford-Fulkerson 算法， 2 3这条边的退流将会做 9999 次，极大的影响 算法的效率。而 dinic 算法确可以有效的解决这个问题。下面的讲解只讲解 dinic 的基本原理和实现，不太纠结于证明。 假设有以下的这幅图：先 bfs 一遍 （注意只遍历容量不为 0 的边

33、）， 求出所有节点的层数，用 level 数组 记录。接着就做网络流，其基本原理就是：在现有的 level 基础上，只按照 level 递增 顺序找增广路径，且有一点不同的是当找到一条s-t 的路径的时候，不是直接结束，而是从当前路径上最小层次的顶点 （顶点， 当前路径最大流量的边上的点， 就是下图的 红点或绿点 K）再次寻找可行流 （ 一定要将当前层次的可行流全部找完啊！ ）【下面的原理描述来自国家集训队论文】整个 dfs 过程分为 2 个操作。如果 p的最后一个顶点为汇点，也就是说找到了增广路， 那么对 p增广，注意到增广后一定有一条或多条 p 中的边被删除了。 这时，我们使增广路径 后退

34、至 p 中从源点可到达的最后一个顶点。如果 p 的最后一个顶点不为汇点，那么观察最后那个的顶点u 。若在层次图中存在从u 连出的一条边，比如 （u,v） ，我们就将顶点 v 放入路径 p 中，继续 dfs 遍历；否则，点 u 对之后的 dfs 遍历就没有用了，我们将点 u以及层次图中连到 u的所有边删除，并且在 p 中后 退一个点。Dfs 过程将会不断重复这 2 个操作，直到从源点连出的边全部被删除为止。 整个 dinic 的过程就是不断地先 bfs ，再 dfs ，直到 bfs 不能得到汇点的层数为止。 面给出一个 dfs的图例，图中，红边代表找到的增广路 p 中的边。具体代码实现如下，我用

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

36、形”的角度观察这个问题， 每个单位的流在当前网络中产生的最小费用，等价于当 前网络中 S到T的最小权值路径的权值，即 S到 T最短路的长度。因此，可以用 SPFA 求最短路，每次选择残留网络中最短的增广路进行增广，直到不存 在增广路为止，可以证明找到的最大流的费用一定最小。分析这个算法的时间复杂度， 如果增广次数是 w，每次 SPFA算法在残留网络 G 上的运 行时间是 ，那么总的时间复杂度就是 。用流量控制连通，每次找费用最小的增广路径，这样得到的最大流肯定是费用最小的。这是我对费用流的理解。Noip2008 传纸条因为要找两条不相交的路径让费用最大，我们可以利用费用流的模板来完成。让起点的

37、流量为 2，这样就可以约束只找两条路径，把费用变成负的，这样将最大费用 改为最小费用。因为有向边，不会有流量环，我们可以将 spfa 的迭代改为大于号也行。下面是费用流的模板，希望认真研读。Message.cpp费用流例子：Sdoi 2009 晨跑要求一个路口不能经过两次以上。 那么就把每个点拆成两个分别放在 A 部和 B 部里面。对于每个输入的 x,y,z 连一条 Ax ，By ，流量为 1，费用为 z的边。再从每个 Bi 向 Ai 连一条流量为 1，费用为 0 的边控制只能走一次。 源即 1 ，汇为 n+n。SDOI2010星际竞速这是道图论题是肯定的，图都给你了那么问题在于如何建模 问题

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

39、次 从 st向每个 u 连一条边，容量为 1，费用为 0，以便 u通过( u,v )到达 v那么这个图的最小费用流就是答案求平均费用这个有点无趣啊。人数给定了其实只要求出最少的总时间花费就行了、不用搞什么分数规划。这题费用流的算法是很明显的啦、就是构图很巧妙 N 辆车， M 个工人。把每个工人拆成 N 个点。记为 Ai,j 表示第 i 个工人修倒数第 j 辆车。每个车跟所有 N*M 个工人拆出的点连边。流量为1，费用为 timei,j*k 。源和每辆车连边， N*M 个点和汇连边，流量都为 1 ，费用同为 0。为什么这么构图呢？考虑第 i 个工人，他修第 j 辆车只对后面要修的车有影响，而前面

40、修过的车已经对当前没有影响了。 而这个影响就是后面每个将要修理的车都多等待了 time 的时间。其他边流量都为 1 是显然的，每辆车修一次，每个工人一个时段只能修理一辆车。跑一遍费用流，出解、阅读材料】网络流问题可以说是 OI 中最灵活的问题之一了， 建模方法很多， 但还是有一定规律的囧网络流建模主要分为两类： 直接用最大流建模、 用最大流最小割定理转化为最小割来建模。 这里主要总结的是前一种。（1）增广路思想：应用范围较小， 但是确实有一些模型用增广路思想很容易解释， 用流量平衡思想却很难解释 （比如下面举的例子） 。增广路思想可以概括为： 原题的方案的得出可以很明显地分为一些阶段， 每一阶

41、段都会对一 些变量 （这些变量可能是实的也可能是虚设的） 产生同样的效果值累加， 而这些变量恰好有 各自的限制， 且互不关联。 这刚好相当于网络中的一条从源点到汇点的一条增广路， 对路上 所有边的流量都会增加，且流量有各自限制（容量） ，且互不关联。并且，该模型满足下面 （3）中的两条原则（可行性原则和最优性原则） 。在比较多的时候， 用增广路思想能够解释 的模型往往是一个很明显的“物质路径”模型，某一种物质（可以是实的也可以是虚的）从 源点往汇点“走” ，边上的流量代表物质经过的量。例 1： NOIP2011 观光公交首先， 由于来出发地的时间已知且一定， 所以“旅行时间总和最小”其实就是所

42、有人下车的 时间总和尽可能小，因此，先求出在不用任何加速器（初始）情况下，到达每一站的时间， 设为 Si ，又设 Mi为在第 i 站上车的来的最晚的人来的时间，则很显然可以得到初始的递 推式： Si=maxSi-1, Mi-1+Di-1 （初始的 D 值），边界 S0=0 。下面来看一下 Di 的减少是如何影响 S 值的。看下面这个例子：N=5i ：01234Di （初始）：3432Mi ：12614Si （初始）：0481116现在将 D0 的值减小1 之后：i ： 0 1234Di ： 2 432Mi ： 1 2614Si ： 0 37 1016可以发现， D0 值减小 1 之后， S1.

43、3 的值都减小了 1，而 S4的值不变。这是因为在 D0 减小 1 之前，对于 1=iMi ，D0 若减小 1，显然 S1会减小 1，而由于 S1M1 ， S1=maxS1, M1 ，所以 S1的值减小 1会使得 maxS1, M1减小1，从而 S2的值 减小 1，然后由于初始的 S2M2 ，同样会使得 S3 减小 1，而初始的 S3=M3 ，故 S3 减小 1 不会使得 maxS3, M3 发生变化，所以 S4的值不会受到影响。所以，可以得到： Di 减小 1，会使得 Si+1.j+1 均减小 1，其中 j 是使任意 i+1=kMk 的最大的 j0 值。从这个当中可以发现， 对于原题的每一个

44、可行方案， 必然都是分为若干个阶段， 其中每一阶 段是将某个 Di 值减小 1（当然， 要满足 Di 在减小前 0），每一阶段进行后都会将从 Si+1 开始的连续的一段 S 值都减小 1，恰好可以抽象成一条连续的路径，又因为当Si 减小到=Mi 的时候就必须停止了（准确来说是不能再往后延伸了） ，所以每个 Si 的能够继续延 伸的减小的量都是有限的，为初始的 Si-Mi （如果这个值 0，则取 0），刚好是一个上限。 这很明显是增广路思想。所以，经过整理，可以建立一个网络流模型：设立两个源点 s和 s（其中 s是真正的源点）及汇点 t，连边 ，容量为 K，费用为 0，表示最多只能有 K 个阶段

45、；将每一站 i 拆成两个点 i和 i，连边 ，容量为 max（Si-Mi, 0） ，费用为 0，表示该 点最多只能接受 max（Si-Mi, 0） 次加速器作用；对于所有的 i 满足 1=iN ，连边 ，容量为 INF ，费用为第 i 站下车的人数（这 是因为即使 Si=Mi ，加速器对于本站仍然有效，只是不能继续延伸，所以表示加速器起 的效果的边应该在本站的限制之前） ；对于所有的 i 满足 0=iN-1 ，连边 ，容量为初始 Di ，费用为 0，表示使用加速 器的地方，从下一站开始对 Si 起效果；对于所有的 i 满足 1=iN ，连边 ，容量为 INF，费用为 0，表示加速器作用的结束。

46、 （其实， 0和（N-1） 这两个点是木有任何意义的，可以从图中删掉） 这样，每一阶段加速器的作用都可以表示为一条从s到 t 的增广路，该网络流模型中的各种限制也反应了题目中的限制。 对该网络求最大费用最大流， 得到的总的最大费用从初始的总 旅行时间中减去 （注意总旅行时间是 long long 的），即为答案。可以证明，这个模型符合“两 条原则”，所以是正确的。（2）流量平衡思想：这个思想的应用非常广，可以解释绝大多数网络流模型。所谓流量平衡， 就是指在一个可行流里， 除了源点和汇点外， 其余每个点的入边流量总和都 等于出边流量总和。 可以证明， 一个流是可行流当且仅当其： （ 1）每条边的

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