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.
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.
C As Integer
F As Integer
End TypePrivate Type NODETYPE
L As Integer
P As Integer
End TypeDim Lt(0 To Maxn) As NODETYPE
Dim G(0 To Maxn, 0 To Maxn) As NETTYPE
Dim N As Integer, S As Integer, T As Integer, F As String
Function Find() As Integer ' {寻找已经标号未检查的顶点}
Dim I As Integer
I = 1
While I <= N And Not (Lt(I).L <> 0) And Lt(I).P = 0
INC I
Wend
Find = IIf(I > N, 0, I)
End Function
Function Ford(ByVal A As Integer) As Boolean '{用标号法找增广路径,并求修改量A}
Dim I As Integer, J As Integer, M As Integer, X As Integer
Ford = True
ReDim Lt(0 To 20)
Lt(S).L = S
Do
I = Find()
If I = 0 Then Exit Do
For J = 1 To N
If Lt(J).L = 0 And (G(I, J).C <> 0 Or G(J, I).C <> 0) Then
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 If
Lt(I).P = 1
Next
Loop Until Lt(T).L <> 0M = T
A = MAXINT
Do
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
Loop Until M = S
Ford = False
End FunctionSub Change(ByVal A As Integer) '{调整过程}
Dim M As Integer, J As Integer
M = T
Do
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
Loop Until M = S
End Sub
Sub PRINTX() ' {打印最大流及其方案}
Dim I As Integer, J As Integer, MAX As Integer
End Sub
MAX = 0
For I = 1 To N
If G(I, T).F <> 0 Then MAX = MAX + G(I, T).F
For J = 1 To N
If G(I, J).F <> 0 Then Print I; "'->"; J; " "; G(I, J).F
Next
Next
Print "The Max Stream=" & MAX
End
Sub Process() '{求最大流的主过程}
Dim DEL As Integer, SUCCESS As Boolean
S = 1
T = N
Do
SUCCESS = Ford(DEL)
If SUCCESS Then
PRINTX
Else
Change DEL
End If
Loop Until SUCCESS = True
End SubSub MAIN()
INIT
Process
End Sub
Sub INIT() '{初始化过程,读人有向图,并设置流为0}
Dim Fn As String, I As Integer, J As Integer
Fn = InputBox("Graph File =")
Open Fn For Input As F
Reset F
Line Input #F, N
ReDim G(0 To 20, 0 To 20)
ReDim Lt(0 To 20)
For I = 1 To N
For J = 1 To N
Line Input #F, G(I, J).C
Next
Next
Close F
End Sub
C As Integer 'capacity
F As Integer 'flux
End TypePrivate Type NODETYPE
L As Integer 'label
P As Integer '
End TypeDim Lt(0 To Maxn) As NODETYPE
Dim G(0 To Maxn, 0 To Maxn) As NETTYPE
Dim N As Integer 'node count
Dim S As Integer 'source node number
Dim T As Integer 'target node number
Dim F As String 'string to parse net weightSub INIT() '{初始化过程,读人有向图,并设置流为0}
Dim Fn As String, I As Integer, J As Integer
Fn = InputBox("Graph File =", "请输入数据文件,路径", "D:\1.txt")
Open Fn For Input As #1 'F
'Reset 'F
Line Input #1, F
N = Val(F)
'ReDim G(0 To 20, 0 To 20)
'ReDim Lt(0 To 20)
For I = 1 To N
Line Input #1, F
For J = 1 To N
G(I, J).C = Val(Split(F)(J - 1))
Next
Next
Close #1
End Sub
Function Find() As Integer ' {寻找已经标号未检查的顶点}
Dim I As Integer
I = 1
While I <= N And Not ((Lt(I).L <> 0) And (Lt(I).P = 0))
I = I + 1 'INC I
Wend
Find = IIf(I > N, 0, I)
End Function
Function Ford(A As Integer) As Boolean '{用标号法找增广路径,并求修改量A}
Dim I As Integer, J As Integer, M As Integer, X As IntegerFord = TrueFor I = 0 To Maxn
Lt(I).L = 0
Lt(I).P = 0
NextLt(S).L = SDo
I = Find()
If I = 0 Then Exit Function
For J = 1 To N
If Lt(J).L = 0 And ((G(I, J).C <> 0) Or (G(J, I).C <> 0)) Then
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 If
Lt(I).P = 1
Next
Loop Until Lt(T).L <> 0M = T
A = 32767 'MAXINT
Do
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
Loop Until M = S
Ford = False
End FunctionSub Change(ByVal A As Integer) '{调整过程}
Dim M As Integer, J As Integer
M = T
Do
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
Loop Until M = S
End Sub
Sub PRINTX() ' {打印最大流及其方案}
Dim I As Integer, J As Integer, MAX As Integer
MAX = 0
For I = 1 To N
If G(I, T).F <> 0 Then MAX = MAX + G(I, T).F
For J = 1 To N
If G(I, J).F <> 0 Then Form1.Print I; " ->"; J; " "; G(I, J).F
Next
Next
Form1.Print "The Max Stream=" & MAX
End SubSub Process() '{求最大流的主过程}
Dim DEL As Integer, SUCCESS As Boolean
S = 1
T = N
Do
SUCCESS = Ford(DEL)
If SUCCESS Then
PRINTX
Else
Change (DEL)
End If
Loop Until SUCCESS = True
End SubSub MAIN()
INIT
Process
End Sub