tele.c

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.
*/

#include <stdio.h>

#define oo -30000
#define MAX 3000
#define NDEBUG
#define korisnik(A) ((A) >= n-m ? 1 : 0)

int n,m;
short tablica[MAX][MAX],temp[MAX][MAX],veza[MAX][MAX],cijena[MAX][MAX];
short koliko[MAX],placa[MAX];

int max(int a, int b, int c)
{
  if (a >= b && a >= c) return a;
  if (b >= a && b >= c) return b;
  return c;
}

int dfs(int cvor)
{
  int i,j,k,dokle,ndokle,novi;

  for (i=1;i<=m;i++)
    tablica[cvor][i] = temp[cvor][i] = oo;

  tablica[cvor][0] = 0;

  dokle = 0;

  for (i=0;i<koliko[cvor];i++)
  {
    novi = veza[cvor][i];

    temp[cvor][0] = 0;

    if (korisnik(novi))
    {
      dokle++;

      for (j=1;j<=dokle;j++)
        temp[cvor][j] = max(tablica[cvor][j], temp[cvor][j], tablica[cvor][j-1] - cijena[cvor][i] + placa[novi]);
    }
    else
    {
      ndokle = dfs(novi);

      dokle += ndokle;

      for (j=1;j<=dokle;j++)
        for (k=1;k<=ndokle && j-k>=0;k++)
          temp[cvor][j] = max(tablica[cvor][j], temp[cvor][j], tablica[cvor][j-k] - cijena[cvor][i] + tablica[novi][k]);
    }

    for (j=0;j<=dokle;j++)
    {
      tablica[cvor][j] = temp[cvor][j];
      temp[cvor][j] = oo;
    }
  }

  return dokle;
}

int main(void)
{
  FILE *f;
  int i,j,rjesenje;

  /* Input */
  f=fopen("tele.in","rt");
  fscanf(f,"%d%d",&n,&m);
  for (i=0;i<n-m;i++)
  {
    fscanf(f,"%d",&koliko[i]);
    for (j=0;j<koliko[i];j++)
    {
      fscanf(f,"%d%d",&veza[i][j],&cijena[i][j]);
      veza[i][j]--;
    }
  }
  for (i=n-m;i<n;i++)
  {
    koliko[i] = 0;
    fscanf(f,"%d",&placa[i]);
  }
  fclose(f);

  /* Solve */
  dfs(0);
  rjesenje = m;
  while (tablica[0][rjesenje] < 0) rjesenje--;

#ifndef NDEBUG
  for (i=0;i<n;i++)
  {
    for (j=0;j<n;j++)
      printf("%6d",tablica[i][j]);
    printf("\n");
  }
#endif

  /* Output */
  f=fopen("tele.out","wt");
  fprintf(f,"%d\n",rjesenje);
  fclose(f); return 0;
}