试论网络流算法中模型的优化与选择
试论网络流算法中模型的优化与选择
福建师大附中 周 成[内容摘要] 近年来，在国内信息学竞赛（尤其是国家队选拔赛）、国际信息学竞赛中，多次出现应用网络流算法求解的试题，网络流算法已是信息学奥赛选手必须掌握的算法。本文主要探讨不同网络模型的构造对问题解决的效率的影响，以及如何优化网络模型，提高算法的效率。
[关键词] 网络流，模型，优化，选择。
一、引言
网络流算法是一种高效实用的算法，相对于其它图论算法来说，它的模型更加复杂，编程复杂度也更高。但是它综合了图论中的其它一些算法（如最短路径、宽度搜索算法），因而适用范围也更广，经常能够很好地解决一些搜索与动态规划无法解决的非NP问题。
网络流在具体问题中的应用，最具挑战性的部分是模型的构造，它没用现成的模式可以套用，需要我们对各种网络流的性质了如指掌（比如点有容量、容量有上下限、多重边等等），根据具体的问题发挥我们的创造性。一道问题经常可以建立多种模型，不同的模型对问题的解决效率的影响也是不同的，本文通过实例探讨如何确定适当的模型，提高网络流算法的效率。
二、网络流算法时间效率
当我们确定问题可以使用最大流算法求解后，就根据常用的Ford-Fulkerson标号法求解；而最小（大）费用最大流问题也可用类似标号法的对偶算法解题。Ford-Fulkerson标号法的运行时间为O（VE2），对偶法求最小费用流的运行时间大约为O（V3E2）。
显然，影响网络流算法的时间效率的因素主要是网络中顶点的数目与边的数目。这二个因素之间不是相互独立的，而是相互联系，矛盾而统一的。在构造网络模型中，有时，实现了某个因素的优化，另外一个因素也随之得到了优化；有时，实现某个因素的优化却要以增大另一因素为代价。因此，我们在具体问题的解决中，要坚持"全局观"，实现二者的平衡。
三、模型的优化与选择
(一)减少模型的顶点数与边数，优化模型
如果能根据问题的一些特殊性质，减少网络模型中的顶点的数目和边的数目，则可以大大提高算法的效率。
例1：最少皇后控制
在国际象棋中，皇后能向八个方向攻击（如图1(a)所示，图中黑点格子为皇后的位置，标有K的格子为皇后可攻击到的格子）。现在给定一个M*N（N、M均不大于于50）的棋盘，棋盘上某些格子有障碍。每个皇后被放置在无障碍的格子中，它就控制了这个格子，除此，它可以从它能攻击到的最多8个格子中选一个格子来控制，如图1(b)所示，标号为1的格子被一个皇后所控制。
请你编一程序，计算出至少有多少个皇后才能完全控制整个棋盘。
图1(a) 图1(b)
输入格式：
输入文件的第一行有两个整数M和N，表示棋盘的行数与列数。接下来M行N列为一个字符矩阵，用'.'号表示空白的格子，'x'表示有障碍的格子。
输出格式：
输出文件的第一行仅有一个数S，表示需要皇后的数目。
Sample Input
3 4
x...
x.x.
.x..
Sample Ouput
5
问题分析]
如果本问题用简单的搜索来做，由于题目给的棋盘很大，搜索算法很难在短时间内出解。由于一个皇后在棋盘最多只能控制两个格子，因此最少需要的皇后数目的下界为[N*
[1] [2] [3] [4]