procedure Print; var a,b :comp; begin;
begin assign(input,'input.txt'); assign(output,'output.txt'); ReadIn;
Work; Print;
rewrite(output); a:=Poss[N,M]; if a=0
then writeln('0/1') else begin
b:=a/2;
while b*2=a do begin a:=b; b:=a/2;
Poss[0,0]:=Poss[0,0]/2; end;
writeln(a:0:0,'/',Poss[0,0]:0:0); end;
close(output);
end;
end.
8. 例6的源程序,“N个人的街道问题”，网络流算法
{$A+,B-,D+,E+,F-,G+,I+,L+,N+,O-,P-,Q+,R+,S+,T-,V-,X+,Y+} {$M 65520,0,655360} program N_Street;
const MaxSize=100; {地图的最大尺寸} var
Row,Col, {地图的行数和列数} N :byte; {人数N} Horiz, {横向的边} Vert : {纵向的边} F
array [1..MaxSize,1..MaxSize] of word; :array [1..MaxSize,1..MaxSize,0..1] of byte;
{F[i,j,d]从点(i,j)向方向d去的流量}
Result :word; {最优结果}
第 26 页 共 29页
procedure ReadIn; var i,j :byte; begin reset(input);
{读入}
readln(Row,Col,N); for i:=1 to Row do begin for j:=1 to Col-1 do
read(Horiz[i,j]);
readln; end;
for j:=1 to Col do begin
for i:=1 to Row-1 do read(Vert[i,j]);
readln; end;
close(input);
end;
procedure Work; var k,i,j :byte; W :array [1..MaxSize,1..MaxSize] of word;
P :array [1..MaxSize,1..MaxSize] of byte;
procedure GetMaxPath; {求最大费用路，用Bellman-Ford迭代法} var i,j :byte; t :integer; Finish :boolean; begin
{迭代终止标志}
fillchar(W,sizeof(W),0); repeat
Finish:=true;
for i:=Row downto 1 do
for j:=Col downto 1 do begin if i begin {横向边} t:=W[i+1,j]; if F[i,j,1]=0 then inc(t,Vert[i,j]); if t>W[i,j] then 第 27 页 共 29页 begin W[i,j]:=t; P[i,j]:=1; Finish:=false; end; if F[i,j,1]>0 then begin {横的逆向边} t:=W[i,j]; if F[i,j,1]=1 then dec(t,Vert[i,j]); if t>W[i+1,j] then begin W[i+1,j]:=t; P[i+1,j]:=3; Finish:=false; end; end; end; if j {纵向边} t:=W[i,j+1]; if F[i,j,0]=0 then inc(t,Horiz[i,j]); if t>W[i,j] then begin W[i,j]:=t; P[i,j]:=0; Finish:=false; end; if F[i,j,0]>0 then begin {纵的逆向边} t:=W[i,j]; if F[i,j,0]=1 then dec(t,Horiz[i,j]); if t>W[i,j+1] then begin W[i,j+1]:=t; P[i,j+1]:=2; Finish:=false; end; end; end; end; until Finish; 第 28 页 共 29页 end; begin fillchar(F,sizeof(F),0); Result:=0; for k:=1 to N do{求的是流量为N的最大费用流} begin GetMaxPath; inc(Result,W[1,1]); {累计费用} i:=1;j:=1; repeat {更新最大费用路上的流量} case P[i,j] of 0: begin inc(F[i,j,0]); inc(j); end; 1: begin 3: inc(F[i,j,1]); inc(i); end; dec(j); 2: begin dec(F[i,j,0]); end; begin dec(i); dec(F[i,j,1]); end; end; until (i=Row) and (j=Col); end; end; begin assign(input,'input.txt'); assign(output,'output.txt'); ReadIn; Work; rewrite(output); writeln(Result); close(output); end. 第 29 页 共 29页