近年来，在国内信息学竞赛（尤其是国家队选拔赛）、国际信息学竞赛中，多次出现应用网络流算法求解的试题，网络流算法已是信息学奥赛选手必须掌握的算法。本文主要探讨不同网络模型的构造对问题解决的效率的影响，以及如何优化网络模型，提高算法的效率。
【关键词】网络流，模型，优化，选择。
【正文】
一、引言
网络流算法是一种高效实用的算法，它综合了图论中的一些经典算法（如最短路径、宽度搜索算法），经常能够很好地解决一些搜索与动态规划无法解决的非NP问题。
运用网络流解决具体问题没用现成的模式可以套用，需要根据网络流的性质发挥创造性探索建立多种模型，通过分析、选择、优化、确定适当的模型，提高网络流算法的效率。
二、网络流算法时间效率
我们知道常用的Ford-Fulkerson标号法求解，运行时间为O（VE2）；而最小（大）费用最大流问题也可用类似标号法的对偶算法解题，其运行时间大约为O（V3E2）。
显然，影响网络流算法的时间效率的因素主要是网络中顶点的数目与边的数目。这二个因素之间不是相互独立的，而是相互联系，矛盾而统一的。在构造网络模型中，有时，实现了某个因素的优化，另外一个因素也随之得到了优化；有时，实现某个因素的优化却要以增大另一因素为代价。因此，我们在具体问题的解决中，要坚�"全局观"，实现二者的平衡。
三、模型的优化与选择
(一)减少模型的顶点数与边数，优化模型
如果能根据问题的一些特殊性质，减少网络模型中的顶点的数目和边的数目，则可以大大提高算法的效率。
例1：最少皇后控制
在国际象棋中，皇后能向八个方向攻击（如图1(a)所示，图中黑点格子为皇后的位置，标有K的格子为皇后可攻击到的格子）。现在给定一个M*N（N、M均不大于于50）的棋盘，棋盘上某些格子有障碍。每个皇后被放置在无障碍的格子中，它就控制了这个格子，除此，它可以从它能攻击到的最多8个格子中选一个格子来控制，如图1(b)所示，标号为1的格子被一个皇后所控制。
请你编一程序，计算出至少有多少个皇后才能完全控制整个棋盘。
 |
|
|
图1(a) 图1(b)
|
[问题分析]
由于题目给的棋盘很大，简单的搜索很难在短时间内出解。同时注意到，一个皇后在棋盘最多只能控制两个格子，因此最少需要的皇后数目的下界为[N*M/2]。要使得皇后数目最少，必定是尽量多的皇后控制两个格子。如果在每两个能相互攻击到的格子之间加上一条有向弧，则问题就转化成类似于二分图的最大匹配问题。
[模型一]
1． 将每个非障碍的格子按行优先编号(0~m*n-1)。
2． 将上述的每个格子i折成两个格子i'和i''，作为网络模型中的顶点。
3． 若格子i可以攻击到格子j且i<j，则在模型中顶点i'到j''之间加上一条有向弧，容量为1。
4． 增加一个源点s，从s点向所有顶点i'添上一条弧；增加一个汇点t，从所有顶点j''到t添上一条弧，容量均为1。
图1(b)所示的棋盘，对应的模型为图2。
图2(点击察看放大图像)
显然，任一解对应于以上模型的一个最大匹配。且最大匹配中，匹配数必定是偶数。因此至少需要的马匹数为M＊N－障碍数－最大匹配数/2。
[模型二]
如果我们将棋盘涂成黑白相间的格子，则某皇后控制的两个格子一定是一个是黑格，另一个是白格（如图3），不妨设这两个格子中皇后在白格子上。于是，我们将N*M个格子分成两部分白格与黑格。因此我们可以将模型一优化为：
图3(点击察看放大图像)
1．将棋盘中的所有格子分成两个部分，对所有的格子进行编号，每个白格与它能攻击到的黑格之间（障碍除外）添上一条从白格到黑格的弧，构成一个二分图。
2．增加一个源点s，从s点向所有非障碍的白格添上一条弧；增加一个汇点t，从所有非障碍的黑格到t添上一条弧。
3．设置所有的弧的流量为1。
图1(b)所示的棋盘，对应的模型为图4。
图4(点击察看放大图像)
[两种模型的比较]
显然，模型二的顶点数与边数大致是模型一的一半。下面是在BP环境下两种模型的时间效率比较(P166/32M)：
|
模型一
|
模型二
|
|
|
m,n=30
|
2.20 s
|
0.77s
|
|
m,n=40
|
7.42s
|
2.25s
|
|
m.n=45
|
12.14s
|
3.52s
|
|
m.n=50
|
18.85s
|
5.27s
|
|
可扩展性
|
不易打印出一种解
|
容易打印出一种解
|
模型二正是根据问题的特殊性（即马的走法），将网格中的格点分成白与黑两类，且规定马只能从白格跳到黑格，从而避免将每个格点折分成两个点，减少模型的顶点数，同时也大大减少了边的数目。达到了很好的优化效果。
(二)综合各种模型的优点，智能选择模型
有时，同一问题的各种模型各有特色，各有利弊。这种情况下，我们就要综合考虑各种模型的优缺点，根据测试数据智能地选择问题的模型。
例2 火星探测器（IOI97）
有一个登陆舱（POD），里边装有许多障碍物探测车（MEV），将在火星表面着陆。火星表面上的登陆舱POD和传送器之间的位置用网格P＊Q表示，登陆舱的位置总是在（1,1），传送器的位置在（P，Q）。着陆后，探测车离开登陆舱向相距不远的先期到达的传送器（Transmitter）移动，MEV一边移动，一边采集岩石（ROCK）标本，岩石由第一个访问到它的MEV所采集，每块岩石只能被采集一次。但是这之后，其他MEV可以从该处通过。探测车MEV不能通过有障碍的地面。如图5所示，其中标志R的格子表示岩石，灰色的格子表示有障碍。
本题限定探测车MEV只能沿着格子向南或向东从登陆处向传送器transmitter移动，允许多个探测车MEV在同一时间占据同一位置。
任务：计算出所有探测车的移动途径，使其送到传送器的岩石标本的数量最多，且使得所有的探测车都必须到达传送器。
[模型一]
很自然地我们以登陆舱的位置为源点，传送器的位置为汇点。同时某块岩石由第一个访问到它的MEV所采集，每块岩石只能被采集一次。但是这之后，其他MEV可以从该处通过，且允许多个探测车MEV在同一时间占据同一位置。因此我们将地图中的每个点分成两个点，即（x,y）à(x,y,0)和(x,y,1)。具体的描述一个火星地图的网络模型构造如下：
1． 将网格中的每个非障碍点分成(x,y)两个点(x,y,0)和(x,y,1)，其中源点s = v(1, 1, 0),汇点t = v(MaxX,
MaxY, 1)。
2． 在以上顶点中添加以下三种类型的边e1,e2,e3，相应地容量和费用分别记为C1、C2、C3以及W1、W2、W3:
u e1 = v(x, y, 0) -> v(x, y, 1),c1 = MaxInt,w1 = 0。
u e2 = v(x, y, 0) -> v(x, y, 1)，c2 = 1，w2 = -1（这里要求(x, y)必须是岩石）
u e3 = v(x, y, 1) -> v(x', y', 0)，c3 = MaxInt,w3 = 0.
其中x'=x+1 y'=y 或x'=x y'=y+1,1 <= x' <= MaxX，1 <= y' <= MaxY，且(x'
y')非障碍。
从以上模型中可以看出，在构造的过程中，将地图上的一个点"拆"成了网络的两个节点。添加e1型边使得每个点可以被多次访问，而添加e2型边使得某点上的岩石对于这个网络，从s到t的一条路径可以看作是一辆探测车的行动路线。路径费用就是探测车搜集到的岩石的数目。对于网络G求流量为NumberOfVehicles的固定最小费用流，可以得到问题的解。
[模型二]
事实上，如果我们只考虑这NumberOfVehicles辆车中每辆车分别依次装上哪些岩石。则每辆车经过的岩石就是一条流，因此我们以网格中的岩石为网络的顶点建立以下的网络流模型。
1. 将网格中的每个起点(网格左上角)能到达，且能从它能到达终点(右下角)的岩石 (x,y)点分成左点(x,y,0)和右点(x,y,1)两个点，并添加源点s和汇点t。
2. 在以上顶点中添加以下五种类型的边e1,e2,e3，相应地容量和费用分别记为C1、C2、C3以及W1、W2、W3:
u e1 = v(x, y, 0) -> v(x, y, 1),c1 = 1,w1 = -1。
u e2 = v(x, y, 1) -> v(x', y', 0)，c2 = 1，w2 = 0（岩石点(x, y)可到达岩石点(x',y')）。
u e3 = s -> v(x, y, 0)，c3 = 1,w3 = 0。
u e4 = v(x, y, 1)->t，c4 = 1,w4 = 0。
u e5=S->t,c5=MaxInt,w5=0。
由于每个石块被折成两个点，且容量为1，就保证了每个石块只被取走一次，同时取走一块石块就得到-1的费用。因此对以上模型，我们求流量为NumberOfVehicles的最小费用流，就可得到解。
[两种模型的比较]
1.模型一以网格为顶点，模型二以岩石为顶点，因此在顶点个数上模型二明显优于模型一，对于一些岩石比较稀疏，而网格又比较大的数据，模型二的效率要比模型一来得高。且只要岩石的个数不超过一定数目，模型二可以处理P，Q很大的数据，而模型一却不行。
2．模型一中边的数目最多为3*P*Q，而模型二中边的数目最坏情况下大约为p*q*(p+1)*(q+1)/4-p*q。因此在这个问题中，若对于一些岩石比较密集且网格又比较大的数据，模型二的边数将大大超过模型一，从而使得时间效率大大低于模型一。
下面是网格中都是岩石的情况比较（PIII700/128M ，BP7.0保护模式）：
|
NumberOfVehicles＝10
|
模型一
|
模型二
|
|
P，Q＝10
|
0.05s
|
0.11s
|
|
P，Q＝20
|
0.11s
|
6.87s
|
|
P，Q＝30
|
0.49s
|
52.58s
|
|
P，Q＝40
|
1.37s
|
内存溢出
|
|
P，Q＝50
|
4.67s
|
内存溢出
|
|
P，Q＝60
|
8.08s
|
内存溢出
|
|
P，Q＞60
|
内存溢出
|
内存溢出
|
通过以上数据，可知对于P，Q不超过60的情况，模型一都能在10秒内出解。而模型二则对于P、Q＝30的最坏情况下速度就很慢了，且P、Q超过30后就出现内存溢出情况，而无法解决。
因此，对于本题，以上两种模型各有利弊，我们可根据测试数据中岩石稀疏程度来决定建立什么样的模型。若岩石比较稀疏，则可以考虑用建立如模型二的网络模型；若岩石比较密集则建立模型一所示网络模型。然后，再应用求最小费用最大流算法求解。对于P，Q＞60，且岩石比较多情况下，两种模型的网络流算法都无法求解。在实际的应用中问题经常都只要求近似解，此时还可用综合一些其它算法来求解。
四、结束语
综上所述，网络流算法中模型的优化是提高网络流算法效率的根本。我们要根据实际问题，从减少顶点及边的角度综合考虑如何对模型进行优化，选择适当的模型，以提高算法的效率。对于有些题目，解题的各种模型各有优劣时，还可通过程序自动分析测试数据，以决定何种情况下采用何种模型，充分发挥各种模型的优点，以达到优化程序效率的目的。
参考书目
[1] 潘金贵、顾铁成等，《现代计算机常用数据结构和算法》，南京大学出版社，1994
[2] 吴文虎 王建德编著，《实用算法的分析与程序设计》，电子工业出版社，1998