就是网络流啊
用dinic，预留推进都可以的
/*************************************/
网络硫酸法很多的。
网络流算法及其应用
5.1 基本概念
在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立—个网络流模型，然后用最大流算法高效地解决问题。
1.问题描述 如图5-1所示是联结某产品地v1和销售地v4的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数表示这条运输线的最大通过能力。产品经过交通网从v1到v4。现在要求制定一个运输方案使从v1到v4的产品数量最多。
图5-1 图5-2
2.网络与网络流
给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点，对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。如图5-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。 所谓网络上的流，是指定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。如图5-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。
3.可行流与最大流
在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有：
(1)容量约束：0≤fij≤cij，(vi,vj)∈E，
(2)守恒条件
对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量vs(f)=汇点的净流入量（-vt(f)）
的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。
网络N中流值最大的流f*称为N的最大流。
4.可增广路径
所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。
设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件：
(1)在p上的所有前向弧(vi→vj)都是非饱和弧，即0≤fij<cij
(2)在p上的所有后向弧(vi←vj)都是非零弧，即0<fij≤cij
则称p为(关于可行流f的)一条可增广路径。
5.最大流定理
当且仅当不存在关于f*的增广路径，可行流f*为最大流。
5. 2 最大流算法
算法思想:最大流问题实际上是求一可行流{fij}，使得v(f达到最大。若给了一个可行流f，只要判断N中有无关于f的增广路径，如果有增广路径，改进f， 得到一个流量增大的新的可行流；如果没有增广路径，则得到最大流。
1.寻求最大流的标号法(Ford,Fulkerson)
从一个可行流(一般取零流)开始，不断进行以下的标号过程与调整过程，直到找不到关于f的可增广路径为止。
(1)标号过程
在这个过程中，网络中的点分为已标号点和未标号点，已标号点又分为已检查和未检查两种。每个标号点的标号信息表示两个 部分：第一标号表明它的标号从哪一点得到的，以便从vt开始反向追踪找出也增广路径；第二标号是为了表示该顶点是否已检查过。
标号开始时，给vs标上(s，0)，这时vs是标号但末检查的点，其余都是未标号的点，记为(0，0)。
取一个标号而未检查的点vi，对于一切未标号的点vj：
A．对于弧(vi，vj)，若fij<cij，则给vj标号(vi，0)，这时，vj点成为标号而未检查的点。
B．对于弧(vi，vj)，若fji>0，则给vj标号(-vi，0)，这时，vj点成为标号而未检查的点。
于是vi成为标号且已检查的点，将它的第二个标号记为1。重复上述步骤，一旦vt被标上号，表明得到一条从vi到vt的增广路径p，转入调整过程。
若所有标号都已检查过去，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。
(2)调整过程
从vt点开始，通过每个点的第一个标号，反向追踪，可找出增广路径P。例如设vt的第一标号为vk(或-vk)，则弧(vk，vt)(或 相应地(vt，vk))是p上弧。接下来检查vk的第一标号，若为vi(或-vi)，则找到(vi，vk)(或相应地(vk，vi))。再检查vi的第一 标号，依此类推，直到vs为止。这时整个增广路径就找到了。在上述找增广路径的同时计算Q：
Q=min{min(cij-fij)，minf*ij}
对流f进行如下的修改：
f'ij = fij+Q (vi，vj)∈ P的前向弧的集合
f'ij = fij-Q (vi，vj)∈ P的后向弧的集合
f'ij = f*ij (vi，vj)不属于P的集合
接着，清除所有标号，对新的可行流f’，重新进入标号过程。
例1:下图表示一个公路网,V1是某原材料产地,V6表示港口码头,每段路的通过能力(容量)如图上的各边上的数据,找一运输方案,使运输到码头的原材料最多?
程序如下:
Program Max_Stream;
Const Maxn=20;
type
nettype=record
C,F:integer;
end;
nodetype=record
L,P:integer;
end;
var
Lt:array[0..maxn] of nodetype;
G:Array[0..Maxn,0..Maxn] of Nettype;
N,S,T:integer;
F:Text;
Procedure Init;{初始化过程，读人有向图，并设置流为0}
Var Fn :String;
I,J :Integer;
Begin
Write( 'Graph File = ' ); Readln(Fn);
Assign(F,Fn);
Reset(F);
Readln(F,N);
Fillchar(G,Sizeof(G) ,0);
Fillchar(Lt,Sizeof(Lt),0);
For I:=1 To N Do
For J:=1 To N Do Read(F,G[I,J].C);
Close(F);
End;
Function Find: Integer; {寻找已经标号未检查的顶点}
Var I: Integer;
Begin
I:=1;
While (I<=N) And Not((Lt[I].L<>0)And(Lt[I].P=0)) Do Inc(I);
If I>N Then Find:= 0 Else Find:= I;
End;
Function Ford(Var A: Integer):Boolean;
Var {用标号法找增广路径，并求修改量A}
I,J,M,X:Integer;
Begin
Ford:=True;
Fillchar(Lt,Sizeof(Lt),0);
Lt[S].L:=S;
Repeat
I:= Find;
If i=0 Then Exit;
For J:=1 To N Do
If (Lt[J].L= 0)And((G[I,J].C<>0)or(G[J,I].C<>0)) Then
Begin
if (G[I,J].F<G[I,J].C) Then Lt[J].L:= I;
If (G[J,I].F>0) Then Lt[J].L:=-I;
End;
Lt[I].P:=1;
Until (Lt[T].L<>0);
M:=T;A:=Maxint;
Repeat
J:=M;M:=Abs(Lt[J].L);
If Lt[J].L<0 Then X:= G[J,M].F;
If Lt[J].L>0 Then X:= G[M,J].C- G[M,J].F;
If X<A Then A:= X;
Until M= S;
Ford:=False;
End;
Procedure Change(A: Integer);{调整过程}
Var M, J: Integer;
Begin
M:= T;
Repeat
J:=M;M:=Abs(Lt[J].L);
If Lt[J].L<0 Then G[J,M].F:=G[J,M].F-A;
If Lt[J].L>0 Then G[M,J].F:=G[M,j].F+A;
Until M=S;
End;
Procedure Print; {打印最大流及其方案}
VAR
I ,J: Integer;
Max: integer;
Begin
Max:=0;
For I:=1 To N DO
Begin
If G[I,T].F<>0 Then Max:= Max + G[I,T].F;
For J:= 1 To N Do
If G[I,J].F<>0 Then Writeln( I, '-> ' ,J,' ' ,G[I,J].F);
End;
Writeln('The Max Stream=',Max);
End;
Procedure Process;{求最大流的主过程}
Var Del:Integer;
Success:Boolean;
Begin
S:=1;T:=N;
Repeat
Success:=Ford(Del);
If Success Then Print
Else Change(Del);
Until Success;
End;
Begin {Main Program}
Init;
Process;
End.
测试数据文件(zdl.txt)如下:
6
0 3 5 0 0 0
0 0 1 4 0 0
0 0 0 0 2 0
0 0 0 0 0 5
0 1 0 3 0 2
0 0 0 0 0 0
运行结果如下:
Graph File=zdl.txt
1->2 3
1->3 2
2->4 3
3->5 2
4->6 3
5->6 2
The Max Stream=5