网络流问题实例分析

网络流问题实例分析例1【逃脱问题】一个n*n格栅是由n行和n列结点组成的一个无向图，如图所示。我们用(i，j)表示处于第i行第j列的结点。除了边界结点（即满足i=1，i=n，j=1，或j=n的结点(i，j)），格栅中的所有其它结点都有四个相邻结点。格栅中有m<n*2个起始点(x1，y1)，(x2，y2)，…(xm，ym)。一条逃脱路径是一个起始点到边界上任意一点的路径。逃脱问题就是找出最多的k条不相交的逃脱路径，k称为逃脱数。上图就是k=10的逃脱方案。输入：第1行

nm

以下m行，其中第i+1行为第i个起点的坐标（xi，yi）

输出：

一个数k，表示逃脱数。构造一个有向图G:由于路径不能相交，所以每个点只能到达一次。为此，可以把原来每个格栅点(i,j)拆分成两个顶点(i,j)1和(i,j)2，在它们之间连一条弧，容量设为1，表示只能到达一次。然后，如果格栅点(x1,y1)与(x2,y2)相邻，则连一条弧<(x1,y1)2,(x2,y2)1>，容量为1。添加两个点S,T表示源和汇，对于图上的起始点和逃脱点（边界上的点）作下面的处理:如果(x,y)是起始点，那么连一条弧<S,(x,y)1>，容量为1；如果(x,y)是逃脱点，那么连一条弧<(x,y)2,T>，容量为1。这样，当我们求出图G的一个流时，它表示了一种逃脱方案，因此,求出最大流的流量就是最多能逃脱的点数了。构图

阿P与阿Q都是四驱车好手，他们各有N辆四驱车。为了一比高下，他们约好进行一场比赛。这次比赛共有M个分站赛，赢得分站赛场次多的获得总冠军。每个分站赛中，两人各选一辆自己的赛车比赛。分站赛的胜负大部分取决于两车的性能，但由于种种原因（如相互之间的干扰），性能并不是决定胜负的唯一指标，有时会出现A赢B、B赢C、C赢D、D又赢A的局面。幸好有一种高智能机器，只要给定两辆四驱车，就能立刻判断谁会赢，在总比赛前它就已经把阿p的每辆车与阿q的每辆车都两两测试过了，并且还把输赢表输入了电脑。另外，由于比赛的磨损，每辆四驱车都有自己的寿命（即它们能参加分站赛的场次），不同的四驱车寿命可能不同，但最多不会超过50场。两辆四驱车最多只能交手一次。现给定N、M（1<=N<=100，1<=M<=1000）、N*N的一个输赢表、每辆四驱车的寿命，并假设每次分站赛两人都有可选的赛车，请你计算一下阿P最多能够赢得多少个分站赛。例2【赛车问题】问题描述

1、建立N个点代表阿P的N辆车，分别以1到N标号；

2、建立N个点代表阿Q的N辆车，分别以N+1到2N标号；

3、如果阿P的第I辆车能够跑赢阿Q的第J辆车，则加一条弧IN+J，容量为1，表示两辆四驱车最多只能交手一次；

4、增加一个源点S，S与1到N中的每一个结点I都连一条弧SI，容量为阿P的第I辆车的寿命；

5、增加一个汇点T，N+1到2N中的每一个结点N+J到T都连一条弧N+JT，容量为阿Q的第J辆车的寿命；

6、再增加一个源点S2，加一条弧S2S，容量为M，表示最多M场分站赛。构图例3【列车调度】

某货运车站有n（n≤20）个车道，由于车道的长度有限，每个车道在某一时刻最多只能停靠一列货运列车。车站正常运行后，每天将有m（m≤100）列货运列车从车站经过，其中第i列列车到达车站的时间为Reach[i]，列车上装有价值Cost[i]的货物。如果准许列车i进站，则BackStreet车站将获得1%×Cost[i]的收益，但由于货物的搬运时间，该列车将在车站停留一段时间Stay[i]，这段时间内，列车将占用车站中的某一个车道；否则列车直接出站，但这样车站将得不到一分钱。你的任务就是：合理的安排列车的进站与出站，使得车站的总获利最大。

{如果列车a从第i车道离开时，列车b刚好到站（即Reach[a]+Stay[a]=Reach[b]），则它不能进入第i车道。}构图

建图方法：

1、将每一列列车拆成两个点，如第i列列车拆成点i和i'；i到i'之间加一条容量为1，费用为1%×Cost[i]的弧ii'；{若ii'的弧的流量为1，则表示该列火车进站，并获得1%×Cost[i]}2、增加一个源点S，S与每个点i连一条容量为1费用为0的弧Si；{如果Si的流量为1，则表示列车i作为某个车道的第一列入站的列车}3、再增加一个源点S’，S’S的容量为n，表示有n个车道；

4、增加一个汇点T，每个点i'与T连一条容量为1费用为0的弧i'T；{如果i’T的流量为1，则表示列车i作为某个车道的最后一列入站的列车}5、对于所有的i和j（i≠j，且i，j∈1..m）,如果Reach[i]+Stay[i]<Reach[j]，则在i’与j之间连一条容量为1，费用为0弧；

{表示可以在某一个车道先停入列车i，等i出站后再停入列车j}

粉红色箭头上的数字表示费用未标数字的弧的费用为0

未标明容量的弧的容量为1优化优化：1.其实没有必要增加一个源点S’及一条弧S’S，因为每次修改可增广轨上弧的流量时，都是以1作为可修改量，故只要规定最多找n次增广轨，就可以确保占用的车道数小于等于n了。2．第1步优化以后，所有弧的容量都变为1，非常便于处理：可以把每条弧的容量和流量用1个Byte类型存储：0——容量为0，流量为0；1——容量为1，流量为0；2——容量为1，流量为1；例4【机器人布阵】

有一个N*M(N,M<=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。墙

Wall草地

Grass

空地

Empty墙

Wall草地

Grass

空地

Empty【模型一】在问题的原型中，草地，墙这些信息不是我们所关心的，我们关心的只是空地和空地之间的联系。因此，我们很自然想到了下面这种简单的模型：以空地为顶点，有冲突的空地间连边，我们可以得到右边的这个图：

问题的求解目标是寻求图G的最大独立集，即求G的独立数α(G)。一般图的α(G)是很难计算的，除非对于一些特殊的图。如完全图Kn的独立数为n,二分完全图Km,n的独立数为max{m,n}。显然这一模型不是属于一些特殊的图，给我们设计算法带来很大的麻烦。【模型二】

我们将每一行，每一列被墙隔开，且包含空地的连续区域称作“块”。显然，在一个块之中，最多只能放一个机器人。我们把水平方向的这些块编上号；同样，把竖直方向的块也编上号。

123451234水平方向的块编号竖直方向的块编号

把每个横向块看作X部的点，竖向块看作Y部的点，若两个块有公共的空地，则在它们之间连边。于是，问题转化成这样的一个二分图：由于每条边表示一个空地，有冲突的空地之间必有公共顶点，所以问题转化为二分图的最大匹配问题。比较前面的两个模型：模型一过于简单，没有给问题的求解带来任何便利；模型二则充分抓住了问题的内在联系，巧妙地建立了二分图模型。为什么会产生这种截然不同的结果呢？其一是由于对问题分析的角度不同：模型一以空地为点，模型二以空地为边；其二是由于对原型中要素的选取有差异：模型一对要素的选取不充分，模型二则保留了原型中“棋盘”这个重要的性质。由此可见，要素的选取，分析角度的不同影响了理论体系的选择。这两点都是图论建模至关重要的步骤。例5【障碍物探测车】

有一个登陆舱（POD）,里边装有许多障碍物探测车（MEV），将在火星表面登陆。着陆后，探测车离开登陆舱向相距不远的先期达到的传送器(Transmitter)移动。MEV一边移动，一边采集岩石（Rock）标本，岩石由第一个访问到它的MEV采集，每块岩石只能被采集一次。但是这之后，….问题可简述为：在PQ的矩形中，每个格子的地形可能是下列三种之一：（1）障碍：无法通过；（2）平地：平坦无物，可通过；（3）石块：可通过，第一次通过时可采到一块岩石；求M条的路径（M给定），使得路径能够覆盖到石块数总和最大，路径要满足的条件是：（1）每条路径都是从(1,1)到(P,Q)，途中每步只能向东或向南走一格；（2）路径不通过障碍。样例输入图示。（探测车数M=2）

样例输出图示：(覆盖到石块数为3)【障碍物探测车分析】1．本题的难点就在于多辆探测车之间的配合问题，而对于只有一辆探测车的退化情况，应用动态规划可得到最优解:

用二维数组map[1..p,1..q]0f0..2表示火星表面情况：

map[i,j]=0表示位置（i,j）为平地；

map[i,j]=1表示位置（i,j）为障碍；

map[i,j]=2表示位置（i,j）为岩石。设S[i,j]表示探测车从（1，1）位置移动到（i,j）位置所能够采集到的岩石标本数目的最大值。则有动态规划方程如下：S[i,j]=Max{s[i-1,j],s[i.j-1]},map[i,j]=0;0,map[i,j]=1;(1≤i≤p,1≤j≤q)Max{s[i-1,j],s[i.j-1]}+1;map[i,j]=2;边界条件：s[i,0]=0,s[0,j]=0(1≤i≤p,1≤j≤q)2.当m≥2时，对m辆探测车各使用一次上述的动态规划算法，就可以得到一个较优解。由于这种简单的贪心没有顾及到各探测车之间的配合，所以不能保证得到最优解，如下面的例子：以上两个算法都是基于一般意义的图G〈V,E〉这一模型上考虑的，如果将一辆探测车的运动看作一条流，因为探测车的数目一定，所以总的流量是确定的。而解的优劣，即采集的标本数量的多少，就只能体现在单位流量的“费用”上了。因此选择使用最小费用最大流的方法求解。3.网络流模型将图G扩充为一个可以求解的网络模型：（1）在建图时，可以略去所有障碍物位置，以及与(1,1)、(p,q)不连通的位置，也可看作障碍物（探测车不会经过）。其余的位置（平地和岩石）都作为图G的顶点。顶点集V={Vi,j│1≤i≤p,1≤j≤q,map[i,j]≠1}；有向边集E={〈vi,j,vi+1,j〉│vi,j∈V,vi+1,j∈V}∪{〈vi,j,vi,j+1〉│vi,j∈V,vi,j+1∈V}。

（2）根据题意再把图G扩充为网络N=〈V,E,C,R〉,C代表网络中各边的容量，R代表各边上单位流量的费用。由于探测车的移动路线可以任意重叠，所以这些边的容量C=∞，费用R=2。（3）如何体现“采集岩石标本”的特征，对于岩石顶点，先到的探测车采到标本，对后到的探测车来说就是平地，一个顶点怎样来扮演两种不同的角色？我们把岩石顶点Vi,j分出一个顶点V’I,j,并增加3条边：

1)边〈Vij,V’ij〉，容量C(Vij,V’ij)=1,表示标本只能采集一次，费用R(Vij,V’ij,)=0;2)边〈V’ij,Vij+1〉和边〈V’ij,Vi+1j〉，容量都是1，费用都是1。这样，每采集一块岩石，对应的流的代价就会减少1；同时，受容量的限制，每块岩石也最多被采集一次。（4）最后再为网络添加源点和汇点：因为m辆探测车都从（1，1）出发，所以源点s只引出一条边〈s,V1,1〉,容量为∞,费用为0；类似，如果map[p,q]=0,即（p,q）处是平地，则汇点t也只引入一条边〈Vp,q,t〉,容量为∞，费用为0；如果map[p,q]=2,即该处是岩石，则多引一条边〈V’p,q,t〉,容量为1，费用也为1。这样就完成了使用最小费用最大流算法的建模。例6【蚯蚓的游戏问题】

²

问题描述：在一块梯形田地上，一群蚯蚓在做收集食物游戏。蚯蚓们把梯形田地上的食物堆积整理如下：

a(1,1)a(1,2)…a(1,m)a(2,1)a(2,2)a(2,3)…a(2,m)a(2,m+1)a(3,1)a(3,2)a(3,3)…a(3,m+1)a(3,m+2)a(n,1)a(n,2)a(n,3)…a(n,m+n-1)它们把食物分成n行，第1行有m堆食物，每堆的食物量分别是a(1,1),a(1,2),…,a(1,m)；第2行有m+1堆食物，每堆的食物量分别是a(2,1),a(2,2),…,a(2,m+1)；以下依次有m+2堆、m+3堆、…、m+n-1堆食物。【蚯蚓的游戏问题】问题描述续1

现在蚯蚓们选择了k条蚯蚓来测试它们的合作能力(1≤k≤m)。测试方法如下：第1只蚯蚓从第1行选择一堆食物，然后往左下或右下爬，并收集1堆食物。例如从a(1,2)只能爬向a(2,2)或a(2,3)，而不能爬向其他地方。接下来再爬向下一行收集一堆食物，直到第n行收集一堆食物。第1条蚯蚓所收集到的食物量是它在每一行收集到的食物量之和；第2条蚯蚓也从第1行爬到第n行，每行收集一堆食物，爬的方法与第1条蚯蚓类似，但不能碰到第1条蚯蚓所爬的轨迹；一般地，第I条蚯蚓从第1行爬到第n行，每行收集一堆食物，爬的方法与第1条蚯蚓类似，但不能碰到前I-1条蚯蚓所爬的轨迹。这k条蚯蚓应该如何合作，才能使它们所收集到的食物总量最多？收集到的食物总量可代表这k条蚯蚓的合作水平。

【蚯蚓的游戏问题】问题描述续2²

编程任务：给定上述梯形m、n和k的值(1≤k≤m≤30；1≤n≤30)以及梯形中每堆食物的量（小于10的非负整数），编程计算这k条蚯蚓所能收集到的食物的最多总量²

数据输入：输入数据由文件名为input1.*的文本文件提供，共有n+1行。每行的两个数据之间用一个空格隔开。l

第1行是n、m和k的值。l

接下来的n行依次是梯形的每一行的食物量a(i,1),a(i,2),…,a(i,m+i-1),i=1,2,…,n。²

输出：k条蚯蚓所能收集到的食物的最多总量。输入示例输出示例

input1.001322261250211006分析与构图

如果只有一条蚯蚓，我们可以用动态规划解决。但现在有k条蚯蚓，而且这些蚯蚓会相互影响（第I只蚯蚓不能碰到前I-1只蚯蚓的路线），动态规划难以实现。考虑用网络流算法来解决。

首先构造一个初步的网络流图。我们可以把每堆食物看成一个顶点(x,y)，每堆食物的量用c(x,y)表示。第1行的m堆为源点，第n行的m+n-1堆为汇点。对于每个顶点(x,y)，添加一条弧<(x,y),(x+1,y)>，表示蚯蚓能从(x,y)向左下爬到(x+1,y)，并得到该处的食物；再添加另一条弧<(x,y),(x+1,y+1)>，表示蚯蚓能从(x,y)向右下爬到(x+1,y+1)，并得到食物。如图1。

分析与构图续1考察这个图论模型，它只能表示原题中蚯蚓的起点、终点和可行的路线，而且权值（食物量）是属于顶点的。我们无法用前面的求网络流的算法来解决，而且题目中一个关键的条件“蚯蚓爬行路线不能重叠”没有能够表示出来。因此我们还要对这个模型加工。

分析与构图续2考虑到原图的缺陷，我们可以把每个顶点(x,y)拆成两个顶点：(x,y)1和(x,y)2。然后按照下述规则重新构造弧：1.

1

若原来有弧<(x1,y1),(x2,y2