长安欧力威1.2油耗:高分：网络流问题

请问搂主用途，16岁已经上中学吧，高一对吧，通常计算机在高中的最高水平就在这个年龄了。
网络流牵涉到离散数学的很多概念，如果没有这个基础，就算告诉你了你也不能理解的很深刻。
上面已经很多人给了很多参考资料，难道你没有时间去认真看一下吗，既然你知道你能找到到，又何必花那么多分来解决问题呢。
真正的高手擅长于从庞大的信息中分析出自己想要的答案，就算这个领域自己并未接触过。
磨刀不误砍柴功，我只想对你说这些。

算少了，仔细看看的懂得，就是缺了点图。。。遗憾
网络流
引言
在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”是网络应用的重要组成部分。在现代的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已经是很常见的了。

第一章 最大流算法
本章介绍网络流问题中的一个重要组成部分——最大流，并通过实际例子，讨论如何在问题描述的基础上建立一个网络流模型，然后用最大流算法高效地解决问题。

图1

什么是最大流问题呢？可以这样来理解，如图1所示，是连接某产地s和销售地t的交通运输网。每条边(vi, vj)代表从城市vi到vj的运输线，产品经这条边由vi输送到vj，边旁边的数表示这条运输线的最大运送量。产品要经过交通网从s运到t。现在要制定一个运输方案，使得从s运到t的产品数量最多。

第一节 基本概念及相关定理
1、网络与网络流
定义1：网络
给一个有向图G=(V，E)，在V中指定一点，称为源点（source，通常记为vs），和另一点，称为汇点（sink，通常记为vt），其余的点叫作中间点。对于E中的每一条边e(vi，vj)都对应着一个正整数c(vi，vj)（c(vi，vj)>=0，通常简写成cij），称为边e的容量(capacity)。
一个赋权有向图N=(V，E，c，vs，vt)称为一个网络(flow network)。
如图1所给出的赋权有向图N就是一个网络，指定s是源点，t为汇点，边旁的数为cij。
定义2：网络流
网络流(flow，或简称为流)，是指定义在边集E上一个函数f={f(vi，vj)}，并称f(vi，vj)为边(vi，vj)上的流量（简记为fij）。
如图2所示的网络N，边上有两个数，第一个数表示流量fij，第二个数表示容量cij。

图2

2、可行流与最大流
在运输网络的实际问题中，对于流有两个显然的要求：一是每个边上的流量不能超过该边的最大通过能力（即边的容量）；二是中间点的流入流出总量为零。因为对于每个点，运出产品的总量与运进这点的产品总量之差，是这点的净输出量。由于中间点只起中转作用，所以中间点的净输出量一定为零。
也正是因为这样，源点的净流出量和汇点净流入量是必相等，且就是这个方案的总产品输送量。
定义3：可行流
一个流f，满足条件：
(1)容量约束条件：0<=fij<=cij, (vi,vj)属于E；
(2)守恒条件：
对于中间点：流出量=流人量，即对每个i(i<>s,t)，有

对于源点s与汇点t分别有：

这样的流就是网络N上的一个可行流(feasible flow)。
此外，我们把源点vs或汇点vt的净流量称为流f的流量，记为v(f)。
例如，图2中各条有向边e旁所标数对给出了(f(e)，c(e))，相应的f就是图1所示的网络N的一个可行流，其流值v(f)=19。
我们需要的都是可行流，所以今后在没有歧义的情况下，有时就用“流”来表示“可行流”这个概念。
网络N中流量最大的流f*，称为N的最大流(maximum flow)。

3、可增广路径
若给一个可行流f={fij}，把网络中使得fij=cij的边称为饱和边(saturated arc)，fij<cij的边称为非饱和边。把fij=0的边称为零流边(void arc)，fij>0的边称为非零流边。
若p是网络N中联结源点s与汇点t的一条路径，我们定义路的方向（不是边的方向）是从s到t，那么p上的边可以分为两类：一类是边的方向与路方向一致，称为前向边（正向边），前向边的全体记为p+；另一类边与路方向相反，称为后向边（反向边），后向边的全体记为p-。
例如，图2中从s到t的一条路p={s，v2，v3，t}。其中(s, v2)、(v3，t)都是前向边。P+={(s, v2))，(v3，t)}；而(v2，v3)是后向边，p-={(v2，v3)}。
定义4：可增广路径(augmenting path)
设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列两个条件，就称之为（关于可行流f的）一条可增广路径：
1、p中的所有前向边(vi，vj)都是非饱和边，即0<=fij<cij；
2、p中的所有后向边(vi，vj)都是非零边，即0<fij<=cij。
之所以称为可增广路径，是因为可以通过修改这条路径上的流，使得整个网络的流量增加。图2中从s到t的一条路p={s，v2，v3，t}就是一条可增广路径。

4、割及其容量
定义5：割（截集cut）
如果A是V的一个子集，A-=V-A，s属于A，t属于A-，则称边集(A，A-)为网络N的一个割。
显然，若把某一个割的所有边从网络中删除，则从vs到vt的最大流量就只能是零了。所以直观上讲，割是从vs到vt的必经之路。
给处一个割(A，A-)，把其中所有边的容量之和称为这个割的容量，记为c(A，A-)，即

网络N中容量最小的割(A*，A*-)称为N的最小割。

引理1
任何一个可行流的流量v(f)都不会超过任意一个割的容量，即v(f)<=c(A，A-)。
例如，图1中，若A={s}，(A，A-)={(s，v1)，(s，v2)}，c(A，A-)=16+13=29。

又例如下图中的割，容量是26。

图3

5、有关定理
定理1
可行流f*为最大流，当且仅当不存在关于f*的可增广路径。
证明：
（必要性）
显然，如果对于一个可行流存在可增广路径，则该可行流一定不是最大流。
（充分性）
对于一个可行流，如果它没有可增广路径，记网络中从s出发沿可增广边可以到达的顶点集合为S，令T=V-S。则[S,T]为一个割。并且，对于N中的任意边(i,j)，如果它是这个割的前向边，那么它一定是饱和边；如果它是这个割的后向边，那么它一定是零边。所以该可行流的流量正好等于割[S,T]的容量。根据前面的引理（任何一个可行流的流量都不会超过任一割的容量），得到当前这个可行流就是最大流，这个割也是最小割。
#
根据前面的证明，若f*是最大流，则网络中必存在一个割(A*，A*-)，使得v(f*)=c(A*，A*-)，于是有以下重要定理。
定理2
最大流最小割定理：在一个网络N中，从vs到vt的最大流的流量等于分离vs，vt的最小割的容量。

第二节 最大流问题的标号法
最大流问题实际上是求一个可行流{fij}，使得流量v(f)达到最大。
定理1实际上已为我们提供了寻求网络中最大流的一个方法。若给了一个可行流f，只要判断网络N中有无关于f的可增广路径。如果有可增广路径，则可以按某种方法改进f，得到一个流量更大的新的可行流；如果没可有增广路径了，则当前的可行流f就是最大流。
下面用顶点标号法来求解。在标号过程中，有标号的顶点表示是集合S中的点（网络中从s出发沿可增广边可以到达的顶点集合为S），没有标号的点表示不是S中的点。如果vt有标号，则说明找到了一条增广路径；如果标号过程进行不下去，而vt又还没有标号，则说明不存在增广路径，于是就得到了最大流，同时也得到了一个最小割(S, V-S)。

寻求最大流的标号法(Ford-Fulkerson)
从一个可行流（一般可以取零流）开始，不断进行以下的标号过程与调整过程，直到找不到关于当前可行流f的可增广路径为止。
(1)标号过程
在这个过程中，网络中的点被分为已标号点和末标号点。已标号点又分为已检查和未检查两种。每个标号点的标号信息有两个部分：第一个标号（父节点标号）表明它的标号是从哪一点得到的，以便从vt开始反向追踪找出可增广路径；第二标号是为了表示该顶点是否已检查过。
标号开始时，给vs标上(s，0)，这时vs是已标号但未检查的点；其余都是未标号的点，记为(0，0)。
取一个已标号而未检查的点vi，对于一切未标号的点vj：
A、对于边(vi，vj)，若fij<cij，则给vj标号(vi，0)。此时，vj点成为标号而未检查的点。
B、对于边(vj，vi)，若fji>0，则给vj号(-vi，0)。此时，vj点成为标号而未检查的点。
vj都访问好以后，vi就成为已标号且已检查的点，将它的第二个标号记为1。
重复上述布骤，一旦vt被标上号，表明得到一条从vs到vt的可增广路径p，转入调整过程。可增广路径p中的点可以通过第一个标号获得。
若所有标号都已检查过，标号过程进行不下去时，则算法结束，这时的可行流就是最大流。
说了这么多，其实大家应该发现，实际上这就是一个搜索，但它和深搜、广搜都不一样，是随便找一个（按照编号）来进行扩展。只要是非饱和的前向边或非零的后向边都可以扩展下去。这就是找出从源点出发，根据可增广路径的规则，遍历所有从源点vs出发，可以到达的点。
(2)调整过程
从vt点开始，通过每个点的第一个标号，反向追踪，就可找出一条可增广路径p。例如设vt的第一标号为vk，则边(vk，vt)是p上边。接下来再检查vk的第一标号，若为vi(或-vi)，则边是(vi，vk)(或相应地(vk，vi))。再检查vi的第一标号，依此类推，直到访问到vs为止，这时整条可增广路径就找到了。在上述找可增广路径的同时，计算一个值 （最大调整量）：

然后，对流f进行如下的修改：

接着，清除所有标号，对新的可行流f’，重新进入标号过程。

第三节 最大流标号法的具体实现
(1)数据结构
type
nwtype=record
c,f:integer; {流量上限和实际流量}
end;
stype=record
l,p:integer; {标号（来自哪个点和是否已检查标记）}
end;

(2)程序
const
maxn=100;

type
nwtype=record
c,f:integer;
end;
stype=record
l,p:integer;
end;

var
nw:array[1..maxn,1..maxn] of nwtype; {网络信息}
s:array[1..maxn] of stype; {标号}
n,i,j,chg,vs,vt:integer; {chg是流量改变量}
f:boolean;

function ford:boolean; {如果没有找到可增广路径，就返回true；找到了返回false}
var
i,j,m:integer;
begin
ford:=true;
fillchar(s,sizeof(s),0);
s[vs].l:=vs; {标号初始化}
repeat
i:=1;
while i<=n do
if (s[i].l<>0) and (s[i].p=0) then break {找第一个已标号但未检查的点}
else inc(i);
if i>n then exit; {没有这样的点，返回true}
for j:=1 to n do {试探(vi,vj)}
if (s[j].l=0) and ((nw[i,j].c<>0) or (nw[j,i].c<>0)) then {vj没有标号且(vi,vj)有边}
if nw[i,j].c<>0 then begin {正向边}
if nw[i,j].f<nw[i,j].c then s[j].l:=i; {非饱和边}
end
else if nw[i,j].f>0 then s[j].l:=-i; {反向边，非零边}
s[i].p:=1; {设置vi的已检查标记}
until s[vt].l<>0; {如果vt被标记，跳出循环}
m:=vt; chg:=maxint;
repeat {倒退求调整值chg}
j:=m;
m:=abs(s[j].l);
if s[j].l>0 then i:=nw[m,j].c-nw[m,j].f {正向边}
else i:=nw[j,m].f; {反向边}
if i<chg then chg:=i;
until m=vs;
ford:=false; {返回false，表示找到可增广路径}
end;

procedure print;
var
i,j,max:integer;
begin
max:=0;
for i:=1 to n do begin
if nw[i,vt].f<>0 then max:=max+nw[i,vt].f; {通过汇点vt来累加最大流值}
for j:=1 to n do
if (nw[i,j].f<>0) and (nw[i,j].c>0) then writeln(i,'->',j,':',nw[i,j].f); {输出正向的流}
end;
writeln(max);
close(input);
halt;
end;

procedure change; {调整}
var
j,m:integer;
begin
m:=vt;
repeat
j:=m;
m:=abs(s[j].l);
if s[j].l>0 then begin nw[m,j].f:=nw[m,j].f+chg; nw[j,m].f:=nw[m,j].f; end
//调整正向边，流量加上chg
else begin nw[j,m].f:=nw[j,m].f-chg; nw[m,j].f:=nw[j,m].f; end;
//调整反向边，流量减少chg
until m=vs;
end;

begin
assign(input,'n1.in'); reset(input);
readln(n);
fillchar(nw,sizeof(nw),0);
for i:=1 to n do
for j:=1 to n do
read(nw[i,j].c);
vs:=1; vt:=n;
repeat
f:=ford; //标号过程
if f then print //没有找到可增广路径，输出最大流，退出程序
else change; //找到可增广路径，进行修改
until false;
end.

注意：此程序只能用于任意两点间至多只有一条有向边的网络。

第四节 最大流标号法改进
如果边上的容量可以是无理数，可以举出例子说明Ford-Fulkerson算法不一定在有限步内终止。
定理3：整流定理
若所有边容量均为正整数，则问题存在最优整数解。
实际上，由于割中前向边的条数最多为n条，因此最大流流量的上界为nU（U表示网络中边上的最大容量）。由于每次增广至少使得流值增加1个单位，因此增广的次数不会超过nU次，算法一定在有限步内终止。此外，由于每次增广最多需要对所有边检查一遍，因此算法的复杂度为O（mnU）。这是一个伪多项式级算法，而不是多项式级算法。
Ford-Fulkerson算法每次只是在所有可增广路径中随便地找一条进行增广，因此增广的次数可能很多。一个自然的想法是：如果每次都找一条增广容量最大的可增广路径，则总的增广次数应当减少。这样的算法称为最大容量增广路算法。
最大容量增广路算法将总的增广次数从Ford-Fulkerson算法的O（nU）次降为了O（mlogU）次，因此是一种多项式时间算法。由于最大容量增广路算法每次需要在网络中寻找最大容量增广路（可以用最短路算法），因此每次增广的时间花费增加了。
与最大容量增广路算法相似的，一个自然的想法是：如果每次都找一条包含边数最少的增广路（称为最短增广路），则算法效果如何？这样的算法称为最短增广路算法。最短增广路算法最多经过O（mn）次增广后终止。
对于这个特殊的最短路问题，我们可以很容易构造最短路算法，在O（m）的时间内找到一条最短增广路（采用从节点s或t开始的广度优先搜索），因此这种实现方法的时间复杂度为O（m2n）。
另外，还可以在O（n）的时间内找到一条最短增广路，即算法的总复杂度为O（mn2）。甚至可以设计出在O（logn）的平均时间内找到一条最短增广路，即算法的总复杂度可降为O（mnlogn）。

不知道你是不是要考noip,如果是，建议你去www.noip.com.cn给那里的教练发个邮件，毕竟那里的老师是专业的，讲得会很清楚的
至于具体的解答，我也不太清楚
如果你真的考noip，不知能不能和我交流一下
qq235035435注明noip就行了

一、引言

网络流算法是一种高效实用的算法，相对于其它图论算法来说，它的模型更加复杂，编程复杂度也更高。但是它综合了图论中的其它一些算法（如最短路径、宽度搜索算法），因而适用范围也更广，经常能够很好地解决一些搜索与动态规划无法解决的非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*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

显然，任一解对应于以上模型的一个最大匹配。且最大匹配中，匹配数必定是偶数。因此至少需要的马匹数为m＊n－障碍数－最大匹配数/2。

[模型二]

如果我们将棋盘涂成黑白相间的格子，则某皇后控制的两个格子一定是一个是黑格，另一个是白格（如图3），不妨设这两个格子中皇后在白格子上。于是，我们将n*m个格子分成两部分白格与黑格。因此我们可以将模型一优化为：

图3

1．将棋盘中的所有格子分成两个部分，对所有的格子进行编号，每个白格与它能攻击到的黑格之间（障碍除外）添上一条从白格到黑格的弧，构成一个二分图。

2．增加一个源点s，从s点向所有非障碍的白格添上一条弧；增加一个汇点t，从所有非障碍的黑格到t添上一条弧。

3．设置所有的弧的流量为1。
图1(b)所示的棋盘，对应的模型为：

图4

[两种模型的比较]

显然，模型二的顶点数与边数大致是模型一的一半。下面是在bp环境下两种模型的时间效率比较(p166/32m)：

模型一 模型二

可扩展性 不易打印出一种解 容易打印出一种解

模型二正是根据问题的特殊性（即马的走法），将网格中的格点分成白与黑两类，且规定马只能从白格跳到黑格，从而避免将每个格点折分成两个点，减少模型的顶点数，同时也大大减少了边的数目。达到了很好的优化效果。

(二)综合各种模型的优点，智能选择模型

有时，同一问题的各种模型各有特色，各有利弊。这种情况下，我们就要综合考虑各种模型的优缺点，根据测试数据智能地选择问题的模型。

例2火星探测器（ioi97）

有一个登陆舱（pod），里边装有许多障碍物探测车（mev），将在火星表面着陆。着陆后，探测车离开登陆舱向相距不远的先期到达的传送器（transmitter）移动，mev一边移动，一边采集岩石（rock）标品，岩石由第一个访问到它的mev所采集，每块岩石只能被采集一次。但是这之后，其他mev可以从该处通过。探测车mev不能通过有障碍的地面。
本题限定探测车mev只能沿着格子向南或向东从登陆处向传送器transmitter移动，允许多个探测车mev在同一时间占据同一位置。

任务：计算出所有探测车的移动途径，使其送到传送器的岩石标本的数量最多，且使得所有的探测车都必须到达传送器。

输入：

火星表面上的登陆舱pod和传送器之间的位置用网络p和q表示，登陆舱pod的位置为（1，1）点，传送器的位置在（p，q）点。

火星上的不同表面用三种不同的数字符号来表示：

0代表平坦无障碍
1代表障碍
2代表石块。
输入文件的组成如下：
numberofvehicles
p
q
(x1y1)(x2y1)(x3,y1)…(xp-1y1)(xpy1)
(x1y2)(x2y2)(x3,y2)…(xp-1y1)(xpy2)
(x1y3)(x2y3)(x3,y3)…(xp-1y3)(xpy3)
…
(x1yq-1)(x2yq-1)(x3,yq-1)…(xp-1yq-1)(xpyq-1)
(x1yq)(x2yq)(x3,yq)…(xp-1yq)(xpyq)
p和q是网络的大小；numberofvehicles是小于1000的整数，表示由登陆舱pod所开出的探测车的个数。共有q行数据，每行表示火星表面的一组数据，p和q都不超过128。

[模型一]

很自然我们以登陆舱的位置为源点，传送器的位置为汇点。同时某块岩石由第一个访问到它的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不超过60的情况，模型一都能在10秒内出解。而模型二则对于p、q＝30的最坏情况下速度就很慢了，且p、q超过30后就出现内存溢出情况，而无法解决。

因此，对于本题，以上两种模型各有利弊，我们可根据测试数据中矿石稀疏程度来决定建立什么样的模型。若矿石比较稀疏，则可以考虑用建立如模型二的网络模型；若矿石比较密集则建立模型一所示网络模型。然后，再应用求最小费用最大流算法求解。对于p，q＞60，且矿石比较多情况下，两种模型的网络流算法都无法求解。在实际的应用中问题经常都只要求近似解，此时还可用综合一些其它算法来求解。

四、结束语

综上所述，网络流算法中模型的优化是网络流算法提高效率的根本。我们要根据实际问题，从减少顶点及边的角度综合考虑如何对模型进行优化，选择适当的模型，以提高算法的效率。对于有些题目，解题的各种模型各有优劣时，还可通过程序自动分析测试数据，以决定何种情况下采用何种模型，充分发挥各种模型的优点，以达到优化程序效率的目的。

算少了，仔细看看的懂得，就是缺了点图。。。遗憾
网络流
引言
在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”是网络应用的重要组成部分。在现代的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已经是很常见的了。

第一章 最大流算法
本章介绍网络流问题中的一个重要组成部分——最大流，并通过实际例子，讨论如何在问题描述的基础上建立一个网络流模型，然后用最大流算法高效地解决问题。

图1

什么是最大流问题呢？可以这样来理解，如图1所示，是连接某产地s和销售地t的交通运输网。每条边(vi, vj)代表从城市vi到vj的运输线，产品经这条边由vi输送到vj，边旁边的数表示这条运输线的最大运送量。产品要经过交通网从s运到t。现在要制定一个运输方案，使得从s运到t的产品数量最多。

第一节 基本概念及相关定理
1、网络与网络流
定义1：网络
给一个有向图G=(V，E)，在V中指定一点，称为源点（source，通常记为vs），和另一点，称为汇点（sink，通常记为vt），其余的点叫作中间点。对于E中的每一条边e(vi，vj)都对应着一个正整数c(vi，vj)（c(vi，vj)>=0，通常简写成cij），称为边e的容量(capacity)。
一个赋权有向图N=(V，E，c，vs，vt)称为一个网络(flow network)。
如图1所给出的赋权有向图N就是一个网络，指定s是源点，t为汇点，边旁的数为cij。
定义2：网络流
网络流(flow，或简称为流)，是指定义在边集E上一个函数f={f(vi，vj)}，并称f(vi，vj)为边(vi，vj)上的流量（简记为fij）。
如图2所示的网络N，边上有两个数，第一个数表示流量fij，第二个数表示容量cij。

图2

2、可行流与最大流
在运输网络的实际问题中，对于流有两个显然的要求：一是每个边上的流量不能超过该边的最大通过能力（即边的容量）；二是中间点的流入流出总量为零。因为对于每个点，运出产品的总量与运进这点的产品总量之差，是这点的净输出量。由于中间点只起中转作用，所以中间点的净输出量一定为零。
也正是因为这样，源点的净流出量和汇点净流入量是必相等，且就是这个方案的总产品输送量。
定义3：可行流
一个流f，满足条件：
(1)容量约束条件：0<=fij<=cij, (vi,vj)属于E；
(2)守恒条件：
对于中间点：流出量=流人量，即对每个i(i<>s,t)，有

对于源点s与汇点t分别有：

这样的流就是网络N上的一个可行流(feasible flow)。
此外，我们把源点vs或汇点vt的净流量称为流f的流量，记为v(f)。
例如，图2中各条有向边e旁所标数对给出了(f(e)，c(e))，相应的f就是图1所示的网络N的一个可行流，其流值v(f)=19。
我们需要的都是可行流，所以今后在没有歧义的情况下，有时就用“流”来表示“可行流”这个概念。
网络N中流量最大的流f*，称为N的最大流(maximum flow)。

3、可增广路径
若给一个可行流f={fij}，把网络中使得fij=cij的边称为饱和边(saturated arc)，fij<cij的边称为非饱和边。把fij=0的边称为零流边(void arc)，fij>0的边称为非零流边。
若p是网络N中联结源点s与汇点t的一条路径，我们定义路的方向（不是边的方向）是从s到t，那么p上的边可以分为两类：一类是边的方向与路方向一致，称为前向边（正向边），前向边的全体记为p+；另一类边与路方向相反，称为后向边（反向边），后向边的全体记为p-。
例如，图2中从s到t的一条路p={s，v2，v3，t}。其中(s, v2)、(v3，t)都是前向边。P+={(s, v2))，(v3，t)}；而(v2，v3)是后向边，p-={(v2，v3)}。
定义4：可增广路径(augmenting path)
设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列两个条件，就称之为（关于可行流f的）一条可增广路径：
1、p中的所有前向边(vi，vj)都是非饱和边，即0<=fij<cij；
2、p中的所有后向边(vi，vj)都是非零边，即0<fij<=cij。
之所以称为可增广路径，是因为可以通过修改这条路径上的流，使得整个网络的流量增加。图2中从s到t的一条路p={s，v2，v3，t}就是一条可增广路径。

4、割及其容量
定义5：割（截集cut）
如果A是V的一个子集，A-=V-A，s属于A，t属于A-，则称边集(A，A-)为网络N的一个割。
显然，若把某一个割的所有边从网络中删除，则从vs到vt的最大流量就只能是零了。所以直观上讲，割是从vs到vt的必经之路。
给处一个割(A，A-)，把其中所有边的容量之和称为这个割的容量，记为c(A，A-)，即

网络N中容量最小的割(A*，A*-)称为N的最小割。

引理1
任何一个可行流的流量v(f)都不会超过任意一个割的容量，即v(f)<=c(A，A-)。
例如，图1中，若A={s}，(A，A-)={(s，v1)，(s，v2)}，c(A，A-)=16+13=29。

又例如下图中的割，容量是26。

图3

5、有关定理
定理1
可行流f*为最大流，当且仅当不存在关于f*的可增广路径。
证明：
（必要性）
显然，如果对于一个可行流存在可增广路径，则该可行流一定不是最大流。
（充分性）
对于一个可行流，如果它没有可增广路径，记网络中从s出发沿可增广边可以到达的顶点集合为S，令T=V-S。则[S,T]为一个割。并且，对于N中的任意边(i,j)，如果它是这个割的前向边，那么它一定是饱和边；如果它是这个割的后向边，那么它一定是零边。所以该可行流的流量正好等于割[S,T]的容量。根据前面的引理（任何一个可行流的流量都不会超过任一割的容量），得到当前这个可行流就是最大流，这个割也是最小割。
#
根据前面的证明，若f*是最大流，则网络中必存在一个割(A*，A*-)，使得v(f*)=c(A*，A*-)，于是有以下重要定理。
定理2
最大流最小割定理：在一个网络N中，从vs到vt的最大流的流量等于分离vs，vt的最小割的容量。

第二节 最大流问题的标号法
最大流问题实际上是求一个可行流{fij}，使得流量v(f)达到最大。
定理1实际上已为我们提供了寻求网络中最大流的一个方法。若给了一个可行流f，只要判断网络N中有无关于f的可增广路径。如果有可增广路径，则可以按某种方法改进f，得到一个流量更大的新的可行流；如果没可有增广路径了，则当前的可行流f就是最大流。
下面用顶点标号法来求解。在标号过程中，有标号的顶点表示是集合S中的点（网络中从s出发沿可增广边可以到达的顶点集合为S），没有标号的点表示不是S中的点。如果vt有标号，则说明找到了一条增广路径；如果标号过程进行不下去，而vt又还没有标号，则说明不存在增广路径，于是就得到了最大流，同时也得到了一个最小割(S, V-S)。

寻求最大流的标号法(Ford-Fulkerson)
从一个可行流（一般可以取零流）开始，不断进行以下的标号过程与调整过程，直到找不到关于当前可行流f的可增广路径为止。
(1)标号过程
在这个过程中，网络中的点被分为已标号点和末标号点。已标号点又分为已检查和未检查两种。每个标号点的标号信息有两个部分：第一个标号（父节点标号）表明它的标号是从哪一点得到的，以便从vt开始反向追踪找出可增广路径；第二标号是为了表示该顶点是否已检查过。
标号开始时，给vs标上(s，0)，这时vs是已标号但未检查的点；其余都是未标号的点，记为(0，0)。
取一个已标号而未检查的点vi，对于一切未标号的点vj：
A、对于边(vi，vj)，若fij<cij，则给vj标号(vi，0)。此时，vj点成为标号而未检查的点。
B、对于边(vj，vi)，若fji>0，则给vj号(-vi，0)。此时，vj点成为标号而未检查的点。
vj都访问好以后，vi就成为已标号且已检查的点，将它的第二个标号记为1。
重复上述布骤，一旦vt被标上号，表明得到一条从vs到vt的可增广路径p，转入调整过程。可增广路径p中的点可以通过第一个标号获得。
若所有标号都已检查过，标号过程进行不下去时，则算法结束，这时的可行流就是最大流。
说了这么多，其实大家应该发现，实际上这就是一个搜索，但它和深搜、广搜都不一样，是随便找一个（按照编号）来进行扩展。只要是非饱和的前向边或非零的后向边都可以扩展下去。这就是找出从源点出发，根据可增广路径的规则，遍历所有从源点vs出发，可以到达的点。
(2)调整过程
从vt点开始，通过每个点的第一个标号，反向追踪，就可找出一条可增广路径p。例如设vt的第一标号为vk，则边(vk，vt)是p上边。接下来再检查vk的第一标号，若为vi(或-vi)，则边是(vi，vk)(或相应地(vk，vi))。再检查vi的第一标号，依此类推，直到访问到vs为止，这时整条可增广路径就找到了。在上述找可增广路径的同时，计算一个值 （最大调整量）：

然后，对流f进行如下的修改：

接着，清除所有标号，对新的可行流f’，重新进入标号过程。

第三节 最大流标号法的具体实现
(1)数据结构
type
nwtype=record
c,f:integer; {流量上限和实际流量}
end;
stype=record
l,p:integer; {标号（来自哪个点和是否已检查标记）}
end;

(2)程序
const
maxn=100;

type
nwtype=record
c,f:integer;
end;
stype=record
l,p:integer;
end;

var
nw:array[1..maxn,1..maxn] of nwtype; {网络信息}
s:array[1..maxn] of stype; {标号}
n,i,j,chg,vs,vt:integer; {chg是流量改变量}
f:boolean;

function ford:boolean; {如果没有找到可增广路径，就返回true；找到了返回false}
var
i,j,m:integer;
begin
ford:=true;
fillchar(s,sizeof(s),0);
s[vs].l:=vs; {标号初始化}
repeat
i:=1;
while i<=n do
if (s[i].l<>0) and (s[i].p=0) then break {找第一个已标号但未检查的点}
else inc(i);
if i>n then exit; {没有这样的点，返回true}
for j:=1 to n do {试探(vi,vj)}
if (s[j].l=0) and ((nw[i,j].c<>0) or (nw[j,i].c<>0)) then {vj没有标号且(vi,vj)有边}
if nw[i,j].c<>0 then begin {正向边}
if nw[i,j].f<nw[i,j].c then s[j].l:=i; {非饱和边}
end
else if nw[i,j].f>0 then s[j].l:=-i; {反向边，非零边}
s[i].p:=1; {设置vi的已检查标记}
until s[vt].l<>0; {如果vt被标记，跳出循环}
m:=vt; chg:=maxint;
repeat {倒退求调整值chg}
j:=m;
m:=abs(s[j].l);
if s[j].l>0 then i:=nw[m,j].c-nw[m,j].f {正向边}
else i:=nw[j,m].f; {反向边}
if i<chg then chg:=i;
until m=vs;
ford:=false; {返回false，表示找到可增广路径}
end;

procedure print;
var
i,j,max:integer;
begin
max:=0;
for i:=1 to n do begin
if nw[i,vt].f<>0 then max:=max+nw[i,vt].f; {通过汇点vt来累加最大流值}
for j:=1 to n do
if (nw[i,j].f<>0) and (nw[i,j].c>0) then writeln(i,'->',j,':',nw[i,j].f); {输出正向的流}
end;
writeln(max);
close(input);
halt;
end;

procedure change; {调整}
var
j,m:integer;
begin
m:=vt;
repeat
j:=m;
m:=abs(s[j].l);
if s[j].l>0 then begin nw[m,j].f:=nw[m,j].f+chg; nw[j,m].f:=nw[m,j].f; end
//调整正向边，流量加上chg
else begin nw[j,m].f:=nw[j,m].f-chg; nw[m,j].f:=nw[j,m].f; end;
//调整反向边，流量减少chg
until m=vs;
end;

begin
assign(input,'n1.in'); reset(input);
readln(n);
fillchar(nw,sizeof(nw),0);
for i:=1 to n do
for j:=1 to n do
read(nw[i,j].c);
vs:=1; vt:=n;
repeat
f:=ford; //标号过程
if f then print //没有找到可增广路径，输出最大流，退出程序
else change; //找到可增广路径，进行修改
until false;
end.

注意：此程序只能用于任意两点间至多只有一条有向边的网络。

第四节 最大流标号法改进
如果边上的容量可以是无理数，可以举出例子说明Ford-Fulkerson算法不一定在有限步内终止。
定理3：整流定理
若所有边容量均为正整数，则问题存在最优整数解。
实际上，由于割中前向边的条数最多为n条，因此最大流流量的上界为nU（U表示网络中边上的最大容量）。由于每次增广至少使得流值增加1个单位，因此增广的次数不会超过nU次，算法一定在有限步内终止。此外，由于每次增广最多需要对所有边检查一遍，因此算法的复杂度为O（mnU）。这是一个伪多项式级算法，而不是多项式级算法。
Ford-Fulkerson算法每次只是在所有可增广路径中随便地找一条进行增广，因此增广的次数可能很多。一个自然的想法是：如果每次都找一条增广容量最大的可增广路径，则总的增广次数应当减少。这样的算法称为最大容量增广路算法。
最大容量增广路算法将总的增广次数从Ford-Fulkerson算法的O（nU）次降为了O（mlogU）次，因此是一种多项式时间算法。由于最大容量增广路算法每次需要在网络中寻找最大容量增广路（可以用最短路算法），因此每次增广的时间花费增加了。
与最大容量增广路算法相似的，一个自然的想法是：如果每次都找一条包含边数最少的增广路（称为最短增广路），则算法效果如何？这样的算法称为最短增广路算法。最短增广路算法最多经过O（mn）次增广后终止。
对于这个特殊的最短路问题，我们可以很容易构造最短路算法，在O（m）的时间内找到一条最短增广路（采用从节点s或t开始的广度优先搜索），因此这种实现方法的时间复杂度为O（m2n）。
另外，还可以在O（n）的时间内找到一条最短增广路，即算法的总复杂度为O（mn2）。甚至可以设计出在O（logn）的平均时间内找到一条最短增广路，即算法的总复杂度可降为O（mnlogn）。