Đề 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.
Recent Comments