LIGHT - Hệ thống đèn
Tác giả: RR
Ngôn ngữ: Pascal
{$R+,Q+}
PROGRAM NKLIGHT;
CONST
fi='';
fo='';
maxn=100;
oo=101;
VAR
m,n:longint;
d,c:array[0..2*maxn+1,0..2*maxn+1] of integer;
trace,dt,xet:array[0..2*maxn+1] of integer;
s,t:longint;
queue:array[1..2*maxn+2] of longint;
first,last:longint;
Procedure ReadInput;
Var
f:text;
i,k:longint;
u,v:longint;
Begin
Assign(f,fi); Reset(f);
Readln(f,m,n,k);
s:=0; t:=m+n+1;
For i:=1 to m do
Read(f,c[s,i]);
For i:=1 to n do
Read(f,c[m+i,t]);
For i:=1 to k do
begin
Readln(f,u,v);
c[u,m+v]:=oo;
end;
Close(f);
End;
Procedure Init;
Var
i:integer;
Begin
Fillchar(xet,sizeof(xet),0);
Fillchar(dt,sizeof(dt),0);
For i:=1 to m+n+1 do trace[i]:=-1;
trace[0]:=0;
first:=1; last:=1;
queue[1]:=s;
xet[s]:=1;
dt[s]:=oo;
End;
Function min(a,b:longint):longint;
Begin
If a<b then min:=a else min:=b;
End;
Procedure FindPath;
Var
i,u:longint;
Begin
While first<=last do
begin
u:=queue[first]; inc(first);
For i:=1 to m+n+1 do
If (c[u,i]>0) and (d[u,i]<c[u,i]) and (xet[i]=0) then
begin
xet[i]:=1;
dt[i]:=min(dt[u],c[u,i]-d[u,i]);
trace[i]:=u;
inc(last); queue[last]:=i;
end
else If (d[i,u]>0) and (xet[i]=0) and (c[i,u]>0) then
begin
xet[i]:=1;
dt[i]:=min(dt[u],d[i,u]);
trace[i]:=-u;
inc(last); queue[last]:=i;
end;
end;
End;
Procedure IncFlow;
Var
x,pre:longint;
Begin
x:=t;
repeat
pre:=trace[x];
If pre>=0 then d[pre,x]:=d[pre,x]+dt[t]
else d[x,-pre]:=d[x,-pre]-dt[t];
x:=abs(pre);
until x=s;
End;
Procedure Solve;
Var
i:integer;
Begin
repeat
Init;
FindPath;
If dt[t]>0 then IncFlow;
until dt[t]=0;
End;
Procedure WriteOutput;
Var
f:text;
p,q,i,j:longint;
cost:longint;
Begin
Assign(f,fo); Rewrite(f);
p:=0; q:=0;
cost:=0;
For i:=1 to m do
If trace[i]=-1 then
begin
cost:=cost+c[0,i];
inc(p);
end;
For i:=1 to n do
If trace[m+i]<>-1 then
begin
cost:=cost+c[m+i,t];
inc(q);
end;
Writeln(f,cost);
{ Writeln(f,p,' ',q);
For i:=1 to m do
If trace[i]=-1 then Writeln(f,i);
For i:=1 to n do
If trace[m+i]<>-1 then Writeln(f,i);}
Close(f);
End;
BEGIN
ReadInput;
Solve;
WriteOutput;
END.