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.