max_flow.pas

最大流算法的pascal实现 非常适合初学者

const
  maxn=30;
type
  nodetype=record
    l{标号标志,为前继节点,>0为相前路,<0为相后路},p{检查标志,1已检查,0未检查}:integer;
           end;
  arctype=record
    c{最大可行流},b{最小可行流},f{实际流}:integer;
          end;
  gtype=array[0..maxn,0..maxn] of arctype;{图}
  ltype=array[0..maxn] of nodetype;{可改进路}
var
  lt:ltype;
  g:gtype;
  n,s,t:integer;
  f:text;
procedure readg;
var
  str:string;
  i,m,j:integer;
begin
  write('file=');
  readln(str);
  assign(f,str);
  reset(f);
  readln(f,n);
  fillchar(g,sizeof(g),0);
  fillchar(lt,sizeof(lt),0);
  for i:=1 to n do
    begin
      for j:=1 to n do read(f,g[i,j].c);
      readln(f);
    end;
  close(f);
end;{读入}
function check:integer;
var
  i:integer;
begin
  i:=s;
  while (i<=t) and not((lt[i].l<>0) and (lt[i].p=0)) do inc(i);{找已标号而未检查的点}
  if i>t then check:=0 else check:=i;
end;
function ford(var a:integer):boolean;
var
  i,j,m,x:integer;
begin
  ford:=true;
  fillchar(lt,sizeof(lt),0);
  lt[s].l:=s;
  repeat{找可扩展路}
    i:=check{找可扩展节点};
    if i=0 then exit{若不可改进则退出};
    for j:=s to t do
      if (lt[j].l=0{若j已被检查}) 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;{引一条从j到i的相前或相后路}
        end;
      lt[i].p:=1;{令i已被检查}
  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-0;
    if lt[j].l>0 then x:=g[m,j].c-g[m,j].f;
    if a>x then a:=x;{找最大允许改进量}
  until m=s;{直到源点}
  ford:=false;
end;
procedure fulkerson(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{若为反相路,减去a);
    if lt[j].l>0 then g[m,j].f:=g[m,j].f+a{否则,加上a};
  until m=s{直到源点};
end;
procedure proceed;
var
  i,j,x,del:integer;
  success:boolean;
begin
  s:=1;
  inc(n,2);
  t:=n;{引一个源点和一个汇点}
  g1:=g;
  fillchar(g,sizeof(g),0);
  for i:=2 to n-1 do
    for j:=2 to n-1 do
      begin
        g[s,i].c:=g[s,i].c+g1[j,i].b;{源点到任意一个节点的限制流为以该节点为终点的最小可行流之和}
        g[i,t].c:=g[i,t].c+g1[i,j].b;{从任意一个节点到汇点的限制流为以该节点为起点的最小可行流之和}
      end;
  for i:=2 to n-1 do
    for j:=2 to n-1 do
      g[i,j].c:=g1[i,j].c-g1[i,j].b;{任意边的限制流为最大可行流减去最小可行流}
  g[2,n-1].c:=maxint;
  g[n-1,2].c:=maxint;{原源点与汇点连一条限制流为无穷大的边}
  repeat
    success:=ford(del);
    if not success then fulkerson(del);
  until success;{求新图的最大流，即为原图的可行流}
  for i:=2 to n-1 do
    for j:=2 to n-1 do
      begin
        g1[i,j].f:=g[i,j].f+g1[i,j].b;{恢复为实际可行流}
      end;
  s:=2;
  dec(n);
  t:=n;{欲求最小流，颠倒源汇点即可}
  g:=g1;
  g[s,t].f:=0;
  g[t,s].f:=0;{恢复原图}
  repeat
    success:=ford(del);
    if not success then fulkerson(del);
  until success;{求最大流}
end;
procedure out;
var
  i,j:integer;
begin
  for i:=1 to n do
    begin
      for j:=1 to n do
        write(g[i,j].f);
      writeln;
    end;
end;{输出}
begin
  readg;
  proceed;
  out;
end.