Una gita al cinema#4463

Una gita al cinema (Editoriale)

Poiché tra ogni coppia di città esiste esattamente un percorso, la rete stradale del paese forma un albero. Per minimizzare le spese totali, conviene a Chip e Dale incontrarsi il prima possibile. Questo accadrà se si incontrano nel loro antenato comune più vicino, dopo di che potranno insieme prendere un taxi per la capitale, dove si trova il cinema.

Implementazione dell'algoritmo

Per trovare l'antenato comune più vicino (LCA) si utilizza il metodo del sollevamento binario (binary lifting). Il grafo è memorizzato come lista di adiacenza nell'array $g$ . Vengono inoltre dichiarati gli array globali necessari per il funzionamento dell'algoritmo LCA:

$d [v]$ — tempo di ingresso nel vertice $v$ durante la ricerca in profondità;
$f [v]$ — tempo di uscita dal vertice $v$ durante la ricerca in profondità;
$d i s t [v]$ dist[v] — distanza dalla radice al vertice $v$ ;
$u p [v] [k]$ up[v][k] — memorizza il $2^{k}$ 2^k-esimo antenato del vertice $v$ ;

#define MAX 100010
#define LOGMAX 18
vector<int> g[MAX];
int timer, d[MAX], f[MAX], dist[MAX];
int up[MAX][LOGMAX];

La funzione dfs esegue una visita in profondità dell'albero, a partire dal vertice $v$ . Il vertice $p$ è il genitore del vertice $v$ . La distanza dalla capitale (vertice numero $1$ ) al vertice $v$ è pari a $l e n$ ; questo valore viene salvato nell'array $d i s t [v]$ dist[v]. Durante la visita vengono inoltre calcolate le etichette di tempo di ingresso e uscita dal vertice — $d [v]$ e $f [v]$ .

void dfs (int v, int p = 1, int len = 0) 
{
  d[v] = timer++;

Salviamo il genitore diretto del vertice $v$ .

  up[v][0] = p;

Salviamo la distanza dalla radice (la capitale) al vertice $v$ .

  dist[v] = len;

Costruiamo la tabella degli antenati binari.

  for (int i = 1; i <= l; i++)
    up[v][i] = up[up[v][i-1]][i-1];

Dal vertice $v$ vengono considerati tutti i possibili passaggi ai vertici adiacenti. Per ogni vertice $t o$ , collegato a $v$ da un arco dell'albero $(v, t o)$ (v, to), viene effettuato il passaggio.

  for (int to : g[v])
    if (to != p) dfs (to, v, len + 1);
  f[v] = timer++;
}

La funzione Parent restituisce vero se il vertice $a$ è un antenato del vertice $b$ .

int Parent(int a, int b)
{
  return (d[a] <= d[b]) && (f[a] >= f[b]);
}

La funzione LCA calcola l'antenato comune più vicino (LCA) di due vertici $a$ e $b$ nell'albero utilizzando il metodo del sollevamento binario e la tabella degli antenati $u p$ .

int LCA (int a, int b) 
{
  if (Parent(a, b)) return a;
  if (Parent(b, a)) return b;
  for (int i = l; i >= 0; i--)
    if (!Parent(up[a][i], b)) a = up[a][i];
  return up[a][0];
}

C++

Parte principale del programma. Leggiamo i dati di input.

scanf("%d %d",&n,&Price);

Calcoliamo il valore $l = ⌈ l o g_{2} n ⌉$ l = ⌈log_2n⌉.

l = 1;
while ((1 << l) <= n)  l++;

Costruiamo il grafo non orientato, che secondo le condizioni del problema rappresenta un albero.

for(i = 0; i < n - 1; i++)
{
  scanf("%d %d",&x,&y);
  g[x].push_back(y);
  g[y].push_back(x);
}

Avviamo sull'albero la ricerca in profondità, a partire dalla capitale dove si trova il cinema.

dfs(1);

Elaboriamo in sequenza $q$ richieste.

scanf("%d",&q);
for(i = 0; i < q; i++)
{
  scanf("%d %d",&x,&y);
  lca = LCA(x, y);

Prima dell'incontro Chip percorrerà $d i s t [x] - d i s t [l c a]$ dist[x] - dist[lca] km, e Dale $d i s t [y] - d i s t [l c a]$ dist[y] - dist[lca] km. Insieme in taxi percorreranno esattamente $d i s t [l c a]$ dist[lca] km.

  Chip = dist[x] - dist[lca];
  Deil = dist[y] - dist[lca];

Calcoliamo e stampiamo le spese finali.

  printf("%.5lf %.5lf\n", (Chip + dist[lca] / 2.0) * Price, 
          (Deil + dist[lca] / 2.0) * Price);
}