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.

Download