МууТуб (Срібло)#10422

МууТуб (Срібло) (Розбір)

Для кожного запиту, заданого парою $(k_{i}, v_{i})$ (k_i, v_i) запустимо пошук в глибину або в ширину, починаючи з вершини $v_{i}$ v_i. При цьому рухатися по графу будемо тільки по ребрам, релевантність яких не менше значення $k_{i}$ k_i. Порахуємо кількість досягнутих вершин $r es$ , не рахуючи початкову вершину $v_{i}$ v_i. Значення $r es$ і буде відповіддю на запит $(k_{i}, v_{i})$ (k_i, v_i).

Приклад

Фермер Джон встановив наступні зв'язки між відео:

Відео $1$ і $2$ мають релевантність $3$ ,
Відео $2$ і $3$ — релевантність $2$ ,
Відео $2$ і $4$ — релевантність $4$ .

На підставі цих даних можна обчислити релевантність між іншими парами відео:

Відео $1$ і $3$ : релевантність = $min (3, 2) = 2$ min(3, 2) = 2,
Відео $1$ і $4$ : релевантність = $min (3, 4) = 3$ min(3, 4) = 3,
Відео $3$ і $4$ : релевантність = $min (2, 4) = 2$ min(2, 4) = 2.

Тепер розглянемо, які відео будуть рекомендовані при наступних запитах:

З відео $2$ при $k = 1$ k = 1 будуть рекомендовані відео $1, 3$ і $4$ .
З відео $1$ при $k = 3$ k = 3 будуть рекомендовані відео $2$ і $4$ .
З відео $1$ при $k = 4$ k = 4 не буде рекомендовано жодне відео.

Реалізація алгоритму — пошук у ширину

Вхідний граф зберігаємо у списку суміжності $g$ .

vector<vector<pair<int, int>>> g;

Функція bfs реалізує пошук у ширину з вершини $s t a r t$ і повертає кількість відвіданих вершин, не включаючи саму початкову вершину $s t a r t$ . У процесі пошуку ми переходимо тільки по тим ребрам, вага яких не менша за задане значення $k$ .

int bfs(int start, int k)
{

Масив найкоротших відстаней у цій задачі не потрібний — досить лише відстежувати, чи була вершина відвідана. Якщо вершина $i$ була відвідана, встановлюємо $u se d [i] = 1$ used[i] = 1.

  vector<int> used(n + 1);
  used[start] = 1;

Ініціалізуємо чергу і додаємо в неї стартову вершину $s t a r t$ .

  queue<int> q;
  q.push(start);

Кількість відвіданих вершин при пошуку у ширину (не рахуючи початкову вершину $s t a r t$ ) підраховуємо в змінній $r es$ .

  int res = 0;

Запускаємо пошук у ширину.

  while (!q.empty())
  {

Виймаємо вершину $v$ з черги $q$ .

    int v = q.front(); q.pop();

Перебираємо ребра, суміжні з вершиною $v$ .

    for (auto edge : g[v])
    {

Розглядаємо ребро $(v, t o)$ (v, to) вагою $k t o$ .

     int to = edge.first;
     int kto = edge.second;

Якщо вага ребра $k t o$ менша $k$ , то таке ребро не розглядаємо (перехід по ньому заборонений).

      if (kto < k) continue;

Якщо вершина $t o$ ще не була відвідана, то додаємо її у чергу, позначаємо як відвідану і збільшуємо лічильник відвіданих вершин $r es$ на $1$ .

      if (used[to] == 0)
      {
        q.push(to);
        used[to] = 1;
        res++;
      }
    }
  }

C++

Повертаємо відповідь на запит.

  return res;
}

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d", &n, &qu);
g.resize(n + 1);
for (i = 0; i < n - 1; i++)
{
  scanf("%d %d %d", &p, &q, &r);

Додаємо у список суміжності неорієнтоване ребро $(p, q)$ вагою $r$ .

  g[p].push_back({ q, r });
  g[q].push_back({ p, r });
}

Послідовно обробляємо $q u$ запитів.

while (qu--)
{
  scanf("%d %d", &k, &v);

Запускаємо пошук у ширину з вершини $v$ . Виводимо кількість вершин, відвіданих в результаті пошуку у ширину.

  printf("%d\n", bfs(v, k));
}

Реалізація алгоритму – пошук у глибину

Вхідний граф зберігаємо у списку суміжності $g$ .

vector<vector<pair<int, int>>> g;

Функція dfs виконує пошук у глибину, починаючи з вершини $v$ , і повертає кількість відвіданих вершин. У процесі пошуку ми переміщаємося тільки по тим ребрам, у котрих вага не менша за задане значення $k$ .

int dfs(int v, int k)
{

Позначаємо вершину $v$ як відвідану.

  used[v] = 1;

У змінній $r es$ підраховуємо кількість вершин, відвіданих у піддереві з коренем у $v$ в ході виконання пошуку у глибину.

  int res = 1;