NKFLOW – SPOJ

Đề bài: http://vn.spoj.com/problems/NKFLOW/

Thuật toán:

• Bài này đơn thuần sử dụng thuật toán luồng. Bạn có thể tham khảo về thuật toán luồn tại:

Code:

{$MODE OBJFPC}
program MaximumFlow;
const
  InputFile  = '';
  OutputFile = '';
  maxN = Round(1E5);
  maxM = Round(1E5);
  maxC = Round(1E9);
type
  TEdge = record
    x, y: Integer;
    c, f: Integer;
    link, link2: Integer;
  end;
var
  fi, fo: TextFile;
  e: array[-maxM..maxM] of TEdge;
  head, head2: array[1..maxN] of Integer;
  level: array[1..maxN] of Integer;
  q: array[1..maxN] of Integer;
  front, rear: Integer;
  n, m, s, t: Integer;
  FlowValue: Int64;

procedure Enter;
var
  i: Integer;
  u, v, capacity: Integer;
begin
  ReadLn(fi, n, m, s, t);
  for i := 1 to m do
    begin
      ReadLn(fi, u, v, capacity);
      with e[i] do
        begin
          x := u; y := v; c := capacity;
        end;
      with e[-i] do
        begin
          x := v; y := u; c := 0;
        end;
    end;
end;

procedure BuildIncidentLists;
var
  i: Integer;
begin
  FillDWord(head[1], n, 0);
  FillDWord(head[2], n, 0);
  for i := -m to m do
    if i <> 0 then
      with e[i] do
        begin
          link := head[x]; head[x] := i;
          link2 := head2[y]; head2[y] := i;
        end;
end;

procedure InitZeroFlow;
var
  i: Integer;
begin
  for i := -m to m do e[i].f := 0;
  FlowValue := 0;
end;

function Min(x, y: Integer): Integer; inline;
begin
  if x < y then Result := x else Result := y;
end;

function cf(const e: TEdge): Integer; inline; //tinh du
begin
  with e do
    Result := c - f;
end;

procedure IncFlow(i: Integer; Delta: Integer); inline; //tang canh i len denta
begin
  Inc(e[i].f, Delta);
  Dec(e[-i].f, Delta);
end;

procedure BuildLevelGraph; //tinh t ve s
var
  u, v, i: Integer;
begin
  FillDWord(level[1], n, 0);
  level[t] := 1;
  q[1] := t;
  front := 1; rear := 1;
  repeat
    u := q[front]; Inc(front);
    i := head2[u];
    while i <> 0 do
      begin
        v := e[i].x; //ke
        if (cf(e[i]) > 0) and (level[v] = 0) then
          begin
            level[v] := level[u] + 1;
            if v = s then Exit;
            Inc(rear);
            q[rear] := v;
          end;
        i := e[i].link2;
      end;
  until front > rear;
end;

function Visit(u: Integer; Delta: Integer): Integer;      // tu s den t
var
  i, v: Integer;
  p, q: Integer;
begin
  if u = t then Exit(Delta);
  if level[u] = 0 then Exit(0);
  q := 0;
  i := head[u];
  while i <> 0 do
    begin
      if (cf(e[i]) > 0) and (level[e[i].y] = level[u] - 1) then
        begin
          v := e[i].y;
          p := Visit(v, Min(Delta, cf(e[i])));
          IncFlow(i, p);
          Inc(q, p);
          Dec(Delta, p);
          if Delta = 0 then Exit(q);
        end;
      i := e[i].link;
    end;
  Result := q;
end;

function AugmentFlow: Integer;
begin
  Result := Visit(s, maxC);
end;

procedure PrintResult;
var
  i: Integer;
begin
  WriteLn(fo, FlowValue);
end;

begin
  AssignFile(fi, InputFile); Reset(fi);
  AssignFile(fo, OutputFile); Rewrite(fo);
  try
    Enter;
    BuildIncidentLists;
    InitZeroFlow;
    repeat
      BuildLevelGraph;
      if level[s] = 0 then Break;
      Inc(FlowValue, AugmentFlow);
    until False;
    PrintResult;
  finally
    CloseFile(fi); CloseFile(fo);
  end;
end.