[Logo] Форум DL
  [DL]  На главную страницу 
Индекс форума ->Олимпиадное программирование ->Обсуждение теории
Автор Сообщение
Тарас Зубык

Темы: 19
Сообщений: 28

Мой профиль
Вот моя прога.
Подскажите, как мне можно максимизировать сумму приоритетво!

{$I-,Q-,R-,S-}
VAR n,m,fin     :integer;
    a,cf,c      :array[0..510,0..510]of longint;
    ff,b,way    :array[0..510]of integer;
    fl          :array[0..510]of boolean;
    f           :text;

Procedure INIT;
var i,j,r,y   :integer;
    k         :longint;
begin
  assign(f,'TRANS.IN'); reset(f);
  readln(f,n,m);
  fin:=510;
  for i:=1 to n do begin
    read(f,k,r);
    c[0,i]:=1; cf[0,i]:=1;
    for j:=1 to r do begin
      read(f,y);
      c[i,n+y]:=1; cf[i,n+y]:=1;
      c[i,0]:=k;
    end;
    readln(f);
  end;
  for i:=1 to m do begin
    readln(f,j);
    c[n+i,fin]:=j; cf[n+i,fin]:=j;
  end;
  close(f);
end;
Procedure OUT;
var i,res :integer;
    sum   :longint;
begin
  assign(f,'TRANS.OUT'); rewrite(f);
  sum:=0; res:=0;
  for i:=1 to n do
    if a[0,i]>0 then begin inc(res); inc(sum,c[i,0]); end;
  writeln(f,res,' ',sum);
  close(f);
end;

Procedure BFS(var min:longint; var kk:integer );
var i,k,r,v     :integer;
begin
  kk:=0;
  for i:=0 to fin do begin b[i]:=0; fl[i]:=true; ff[i]:=0; end;
  fl[0]:=false; k:=1; r:=0;
  while r<k do begin
    inc(r); v:=b[r];
    for i:=0 to fin do
      if fl[i] then if cf[v,i]>0 then begin
        fl[i]:=false; inc(k); b[k]:=i; ff[i]:=v;
      end
  end;
  if fl[fin] then exit;
  kk:=1; way[kk]:=fin; v:=ff[fin]; min:=maxlongint;
  repeat
    if cf[v,way[kk]]<min then min:=cf[v,way[kk]];
    inc(kk); way[kk]:=v;
    v:=ff[v];
  until v=0;
end;
Procedure MAX_FLOW;
var i,x,y,k     :integer;
    min         :longint;
begin
  repeat
    BFS(min,k);
    for i:=k downto 1 do begin
      x:=way[i+1]; y:=way[i];
      inc(a[x,y],min);
      a[y,x]:=-a[x,y];
      cf[x,y]:=c[x,y]-a[x,y];
      cf[y,x]:=c[y,x]-a[y,x];
    end;
  until k=0;
end;

BEGIN
  INIT;
  MAX_FLOW;
  OUT;
END.


Большое спасибо!
______________________
Thinking is positive
 
Индекс форума ->Олимпиадное программирование ->Обсуждение теории
Time:0,031