tele.pas

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

(*
 Izborne pripreme 2002. - 2. izborni ispit - 1. zadatak - TELE
 Rjesenje napisao: Davor Bonaci <[e-mail]>

 OPIS ALGORITMA:
 ===============
 U zadataku potrebno je naci najveci broj korisnika koji mogu gledati prijenos,
 ali da TV kuca ne bude u gubitku.
 Kako je zadano stablo jednog odasiljaca (kojeg oznacavamo KORIJENOM stabla) i
 nekoliko releja, onda neka podstabla mozemo promatrati neovisno, pa vrijedi
 princip optimalnosti, te cemo koristiti dinamicko programiranje za rjesenje
 problema.
 Neka tablica[i][j] oznacava koliko je TV kuca u dobitku (ili gubitku) ako
 utakmicu prikaze tocno j korisnika koji se nalaze u stablu kojem je i-ti relej
 korijen.
 Tada lako konstruiramo rekurzivnu relaciju (vidi donji kod) koja iz poznatih
 rjesenja za svako dijete nekog cvora dobija rjesenje za taj cvor.
 Redoslijed racunanja rjesenja za svaki cvor jednak je DFS obilasku stabla.
 Vremenska slozenost: OK.
 Prostorna slozenost: Za pamcenje stabla u obliku kao sto je prikazan u donjem
 kodu treba nam kvadratna matrica, i jos nekoliko dodatnih matrica, pa je
 prostorna slozenost O(4*N*N + 2*N), sto cini nesto manje od 70 MB memorije.
 Ovo se moglo izvesti unutar 10 MB, koristenjem dinamicke alokacije memorije,
 medjutim to ovdje nije potrebno, jer je i ovo dovoljno dobro za potrebe
 zadatka.
*)

program tele(input, output);

const
  oo = -30000;
  MAX = 3000;

var
  n,m : integer;
  tablica,temp,veza,cijena : array[0..MAX, 0..MAX] of integer;
  koliko,placa : array[0..MAX] of integer;

function korisnik(a : integer) : boolean;
begin
  if (a >= n-m) then korisnik := true else korisnik := false;
end;

function maxi(a, b, c : integer) : integer;
begin
  if ((a >= b) and (a >= c)) then maxi := a
  else if ((b >= a) and (b >= c)) then maxi := b
  else maxi := c;
end;

function dfs(cvor : integer) : integer;
var
  i,j,k,dokle,ndokle,novi : integer;
begin
  for i:=1 to m do
  begin
    tablica[cvor,i] := oo;
    temp[cvor,i] := oo;
  end;

  tablica[cvor,0] := 0;

  dokle := 0;

  for i:=0 to koliko[cvor]-1 do
  begin
    novi := veza[cvor,i];

    temp[cvor,0] := 0;

    if (korisnik(novi)) then
    begin
      inc(dokle);

      for j:=1 to dokle do
        temp[cvor,j] := maxi(tablica[cvor,j], temp[cvor,j], tablica[cvor,j-1] - cijena[cvor,i] + placa[novi]);
    end
    else
    begin
      ndokle := dfs(novi);

      inc(dokle, ndokle);

      for j:=1 to dokle do
        for k:=1 to ndokle do
          if (j-k >= 0) then
            temp[cvor,j] := maxi(tablica[cvor,j], temp[cvor,j], tablica[cvor,j-k] - cijena[cvor,i] + tablica[novi,k])
          else break;
    end;

    for j:=0 to dokle do
    begin
      tablica[cvor,j] := temp[cvor,j];
      temp[cvor,j] := oo;
    end;
  end;

  dfs := dokle;
end;

var
  f : text;
  i,j,rjesenje : integer;
begin
  { Input }
  assign(f, 'tele.in'); reset(f);
  read(f, n, m);
  for i:=0 to n-m-1 do
  begin
    read(f, koliko[i]);
    for j:=0 to koliko[i]-1 do
    begin
      read(f, veza[i,j], cijena[i,j]);
      dec(veza[i,j]);
    end;
  end;
  for i:=n-m to n-1 do
  begin
    koliko[i] := 0;
    read(f, placa[i]);
  end;
  close(f);

  { Solve }
  dfs(0);
  rjesenje := m;
  while (tablica[0,rjesenje] < 0) do dec(rjesenje);

  { Output }
  assign(f, 'tele.out'); rewrite(f);
  writeln(f, rjesenje);
  close(f);
end.