Yoluxma#10367

Yoluxma (Həll təhlili)

Bütün fermaları yoluxdurmaq üçün iki növ əməliyyat yerinə yetirmək lazımdır:

Hərəkətlər. Hər bir yolun ən azı bir dəfə istifadə edilməsi ilə $n - 1$ n - 1 inək göndərilməlidir. Deməli, yalnız fermalar arasında inəkləri hərəkət etdirmək üçün minimum $n - 1$ n - 1 gün tələb olunacaq.
İki qatlama. Fermada əvvəlcə yalnız bir xəstə inək olduğu üçün əvvəlcə iki qatlama əməliyyatları edərək lazım olan sayda inək yetişdirməliyik.

Qeyd edək ki, iki qatlamalar və keçidlər yoluxmadan sonra ağacın fərqli yerlərində baş verə bilər.

Tutaq ki, $v$ fermasına bir xəstə inək gəlib. Əgər $v$ ferması ağacda $x$ uşaqa sahibdirsə, o, $x$ qonşuya xəstə inəklər göndərməlidir, buna görə $x$ inək olmalıdır.

Əvvəlcə $v$ fermasında $1$ inək olur. İki qatlamaları edirik: $1 \to 2 \to 4 \to 8$ 1 \to 2 \to 4 \to 8 ... . $x$ inək əldə etmək üçün minimal iki qatlama sayı $⌈ l o g_{2} x ⌉$ ⌈log_2 x⌉-dir.

Beləliklə, xəstəliyi bütün fermalara yaymaq üçün lazım olan minimal günlər sayı:

(n - 1) + v = 1 \sum n ⌈ l o g_{2} u s \c a q s a y ı s ı d u ¨ y u ¨ n v ⌉

(n - 1) + ∑_{v = 1}^n ⌈log_2~uşaq~sayısı~düyün~v⌉

Təcrübədə, məsələnin şərtinə görə hər bir fermada hər hansı bir zamanda ən azı bir xəstə inək olmalıdır. Şərtə görə, bütün fermaları yoluxdurduqdan sonra hər fermada ən azı bir xəstə inək qalması lazım deyil.

Alqoritmin Tətbiqi

Ağacı qonşuluq siyahısı $g$ şəklində saxlayırıq.

vector<vector<int>> g;

dfs funksiyası $v$ düyünündən başlayaraq dərindən keçmə edərək bu düyündə köklü alt-ağacda yoluxmuş inəkləri iki qatlamaq üçün lazım olan günlərin sayını qaytarır. $v$ düyününün atası $p a r$ -dır.

int dfs(int v, int par = 0)
{
  int ans = 0;
  for (int to : g[v])
    if (to != par)
      ans += dfs(to, v);
  return ans + ceill(log2(g[v].size()));
}

C++

Proqramın əsas hissəsi. Daxil olan məlumatları oxuyuruq. Qrafı qururuq.

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

C++

Düyün $1$ -dən dərindən keçmə axtarışını işə salırıq və bütün fermaları yoluxdurmaq üçün lazım olan minimal günlərin sayını hesablayırıq. Cavabı $r es$ dəyişənində saxlayırıq.

res = dfs(1) + n - 1;

Cavabı çıxarırıq.

printf("%d\n", res);