Kinoya getmək#4463

Kinoya getmək (Həll təhlili)

Hər hansı iki şəhər arasında düz bir yol olduğundan, ölkənin yol şəbəkəsi ağac əmələ gətirir. Ümumi xərcləri minimuma endirmək üçün Çipin və Deylin mümkün qədər tez görüşməsi sərfəlidir. Bu, onlar ən yaxın ümumi əcdadlarında görüşdükdə baş verəcək, bundan sonra onlar kinoteatrın yerləşdiyi paytaxta birlikdə taksi ilə gedə biləcəklər.

Alqoritmin realizasiyası

Ən yaxın ümumi əcdadı (LCA) tapmaq üçün ikilik qalxma metodu istifadə olunur. Qraf $g$ massivində qonşuluq siyahısı şəklində saxlanılır. LCA alqoritminin işləməsi üçün lazımi qlobal massivlər də elan olunur:

$d [v]$ — dərinliyə görə axtarış zamanı $v$ təpəsinə giriş vaxtı;
$f [v]$ — dərinliyə görə axtarış zamanı $v$ təpəsindən çıxış vaxtı;
$d i s t [v]$ dist[v] — kökdən $v$ təpəsinə qədər olan məsafə;
$u p [v] [k]$ up[v][k] — $v$ təpəsinin $2^{k}$ 2^k-cı əcdadını saxlayır;

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

dfs funksiyası $v$ təpəsindən başlayaraq ağacın dərinliyə görə gəzintisini yerinə yetirir. $p$ təpəsi $v$ təpəsinin valideynidir. Paytaxtdan (nömrəsi $1$ olan təpədən) $v$ təpəsinə qədər olan məsafə $l e n$ -ə bərabərdir; bu qiymət $d i s t [v]$ dist[v] massivində saxlanılır. Gəzinti prosesində həmçinin təpəyə giriş və çıxış vaxt möhürləri — $d [v]$ və $f [v]$ hesablanır.

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

$v$ təpəsinin bilavasitə valideynini saxlayırıq.

  up[v][0] = p;

Kökdən (paytaxtdan) $v$ təpəsinə qədər olan məsafəni saxlayırıq.

  dist[v] = len;

İkilik əcdadlar cədvəlini qururuq.

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

$v$ təpəsindən qonşu təpələrə bütün mümkün keçidlər nəzərdən keçirilir. $v$ ilə $(v, t o)$ (v, to) ağac tili ilə birləşdirilmiş hər $t o$ təpəsi üçün keçid yerinə yetirilir.

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

Parent funksiyası, əgər $a$ təpəsi $b$ təpəsinin əcdadıdırsa, doğru qaytarır.

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

LCA funksiyası ağacda iki $a$ və $b$ təpəsinin ən yaxın ümumi əcdadını (LCA) ikilik qalxma metodu və $u p$ əcdadlar cədvəli vasitəsilə hesablayır.

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++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

$l = ⌈ l o g_{2} n ⌉$ l = ⌈log_2n⌉ qiymətini hesablayırıq.

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

Məsələnin şərtinə görə ağac olan yönəldilməmiş qrafı qururuq.

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

Ağac üzərində kinoteatrın yerləşdiyi paytaxtdan başlayaraq dərinliyə görə axtarış işə salırıq.

dfs(1);

$q$ sorğunu ardıcıl olaraq emal edirik.

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

Görüşənə qədər Çip $d i s t [x] - d i s t [l c a]$ dist[x] - dist[lca] km, Deyl isə $d i s t [y] - d i s t [l c a]$ dist[y] - dist[lca] km yol qət edəcək. Birlikdə taksidə onlar düz $d i s t [l c a]$ dist[lca] km yol qət edəcəklər.

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

Yekun xərcləri hesablayıb çap edirik.

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