NKFLOW - Luồng cực đại trên mạng

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
program NKFLOW;
const
  input  = '';
  output = '';
  maxn = 1000;
type
  PNode = ^TNode;
  TNode = record
    adj: integer;
    link: PNode;
  end;
var
  c,f: array[1..maxn,1..maxn] of integer;
  trace,queue: array[1..maxn] of integer;
  n,m,s,t: integer;
  a: array[1..maxn] of PNode;

procedure add(u,v: integer);
var
  P: PNode;
begin
  New(P);
  P^.adj := v;
  P^.link := a[u];
  a[u] := P;
end;

procedure init;
var
  fi: text;
  i,u,v: integer;
begin
  assign(fi, input);
    reset(fi);

  readln(fi, n, m, s, t);
  fillchar(c, sizeof(c), 0);
  fillchar(f, sizeof(f), 0);

  for i := 1 to m do
    begin
      readln(fi, u, v, c[u,v]);
      add(u,v);
    end;

  close(fi);
end;

function FindPath: boolean;
var
  va,st,front,rear: integer;
  u: PNode;
begin
  fillchar(trace, sizeof(trace), 0);
  front := 1;
  rear := 1;
  queue[1] := s;
  trace[s] := -1;

  repeat
    st := queue[front];
    inc(front);
    u := a[st];

    while u <> nil do
      begin
        va := u^.adj;
        if (trace[va] = 0) and (c[st,va] > f[st,va]) then
          begin
            trace[va] := st;
            if va = t then exit(true);

            inc(rear);
            queue[rear] := va;
          end;

        u := u^.link;
      end;
  until front > rear;
  FindPath := false;
end;

procedure IncFlow;
var
  delta,u,v: integer;
begin
  delta := high(longint);
  v := t;

  repeat
    u := trace[v];
    if c[u,v] - f[u,v] < delta then delta := c[u,v] - f[u,v];
    v := u;
  until v = s;

  v := t;
  repeat
    u := trace[v];
    f[u,v] := f[u,v] + delta;
    f[v,u] := f[v,u] - delta;
    v := u;
  until v = s;
end;

procedure FordFulkerson;
begin
  repeat
    if not FindPath then break;
    IncFlow;
  until false;
end;

procedure printresult;
var
  fo: text;
  cost,i,j: integer;
begin
  assign(fo, output);
    rewrite(fo);

  cost := 0;
  for i := 1 to n do
    if f[s,i] > 0 then cost := cost + f[s,i];

  writeln(fo, cost);
  close(fo);
end;

begin
  init;
  FordFulkerson;
  printresult;
end.

Download