一、高分：网络流问题
算少了，仔细看看的懂得，就是缺了点图。。。遗憾
网络流
引言
在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流等等。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）。
