Сервер#10456

Сервер (Розбір)

Граф містить до $1 0^{4}$ 10^4 вершин і до $4 \cdot 1 0^{4}$ 4 \cdot 10^4 ребер, тому зберігатимемо його у вигляді списку суміжності. Усі ваги ребер додатні, отже, найкоротші відстані можна знаходити алгоритмом Дейкстри.

Постановка задачі в термінах графа. Позначимо через $d (a, b)$ довжину найкоротшого шляху між вершинами $a$ і $b$ . Якщо сервер стоїть у місті $v$ , то гість із міста $c_{i}$ c_i отримує затримку $d (c_{i}, v)$ d(c_i, v). Сумарна затримка всіх гостей дорівнює

S (v) = d (c_{1}, v) + d (c_{2}, v) + ... + d (c_{k}, v)

S(v) = d(c_1, v) + d(c_2, v) + ... + d(c_k, v)

Потрібно знайти вершину $v$ з мінімальним значенням $S (v)$ , а при рівності — з найменшим номером.

Чому запускаємо Дейкстру з міст гостей. Можна було б для кожної вершини-кандидата $v$ запустити Дейкстру з $v$ і скласти відстані до $k$ міст гостей. Але кандидатів до $1 0^{4}$ 10^4, і стільки запусків занадто багато. Зауважимо, що граф неорієнтований, тому $d (c_{i}, v) = d (v, c_{i})$ d(c_i, v) = d(v, c_i). Отже, один запуск Дейкстри з міста гостя $c_{i}$ c_i одразу дає затримку цього гостя для всіх можливих місць сервера. Гостей не більше $100$ , достатньо $k$ запусків.

Як накопичується сума. Заведемо масив $s u m [1.. n]$ , спочатку заповнений нулями. Елемент $s u m [v]$ зберігатиме сумарну затримку гостей при розміщенні сервера у вершині $v$ .

Далі для кожного гостя по черзі:

Запускаємо алгоритм Дейкстри з вершини $c_{i}$ c_i і отримуємо масив $d i s t [1.. n]$ dist[1..n], де $d i s t [v] = d (c_{i}, v)$ dist[v] = d(c_i, v). Це затримка $i$ -го гостя, якщо сервер знаходиться в місті $v$ .
Проходимо по всіх вершинах $v = 1, 2, ..., n$ v = 1, 2, ..., n і виконуємо $s u m [v] + = d i s t [v]$ sum[v] += dist[v]. Так ми додаємо внесок $i$ -го гостя до сумарної затримки кожного можливого місця розміщення сервера.

Після обробки всіх $k$ гостей кожен елемент $s u m [v]$ містить рівно $k$ доданків — затримки всіх гостей до вершини $v$ , тобто $s u m [v] = S (v)$ sum[v] = S(v).

Вибір відповіді. Перебираємо вершини $v = 1, 2, ..., n$ v = 1, 2, ..., n у порядку зростання номерів і запам'ятовуємо вершину з мінімальною сумою. Відповідь оновлюємо лише при строгій нерівності $s u m [v] < b es t$ sum[v] < best. Тоді при кількох вершинах з однаковою мінімальною сумою залишиться перша з них, тобто з найменшим номером.

Мінімум шукається по всіх $n$ вершинах, а не лише по містах гостей: оптимальним місцем може виявитися місто, де гостей немає.

Приклад

Граф, наведений у прикладі, має такий вигляд:

Запустимо алгоритм Дейкстри з вершин, у яких проживають гості: $1, 2$ і $5$ . Для кожної з цих вершин визначимо найкоротші відстані до всіх інших міст.

Далі для кожної вершини графа знайдемо суму відстаней до всіх міст із гостями. Мінімальна сума відстаней дорівнює $13$ , і вона досягається у вершині з найменшим номером $2$ .

Таким чином, сервер слід розмістити в місті $2$ . Сумарна відстань від нього до міст, де проживають гості, становить $5 + 0 + 8 = 13$ 5 + 0 + 8 = 13.

Реалізація алгоритму

Оголосимо константу нескінченність.

#define INF 0x3F3F3F3F

Структура $e d g e$ зберігатиме інформацію про ребро: вершину $n o d e$ , у яку веде ребро, і вагу $d i s t$ цього ребра.

struct edge
{
  int node, dist;
  edge(int node, int dist) : node(node), dist(dist) {}
};

Оголосимо компаратор для сортування пар $(n o d e, d i s t)$ (node, dist) за спаданням значення $d i s t$ .

bool operator< (edge a, edge b)
{
  return a.dist > b.dist;
}

Оголосимо список суміжності для представлення графа.

vector<vector<edge> > g;

Функція Dijkstra реалізує алгоритм Дейкстри. На вхід вона приймає граф $g$ і початкову вершину $s t a r t$ . Значенням, що повертається, є масив $d$ , де $d [i]$ містить найкоротшу відстань від вершини $s t a r t$ до вершини $i$ .

void Dijkstra(vector<vector<edge> >& g, vector<int>& d, int start)
{
  priority_queue<edge> pq;
  pq.push(edge(start, 0));

  d = vector<int>(n + 1, INF);
  d[start] = 0;

  while (!pq.empty())
  {
    edge e = pq.top(); pq.pop();
    int v = e.node;

    if (e.dist > d[v]) continue;

    for (auto e : g[v])
    {
      int to = e.node;
      int cost = e.dist;
      if (d[v] + cost < d[to])
      {
        d[to] = d[v] + cost;
        pq.push(edge(to, d[to]));
      }
    }
  }
}

C++

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

scanf("%d %d %d", &n, &m, &k);
c.resize(k);
for (i = 0; i < k; i++)
  scanf("%d", &c[i]);

Читаємо вхідний зважений граф.

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

C++

Запускаємо алгоритм Дейкстри з міст, у яких проживають гості.

dp.resize(n + 1);
for (i = 0; i < k; i++)
{
  Dijkstra(g, dist, c[i]);

  for (j = 1; j <= n; j++)
   dp[j] += dist[j];
}

C++

На даний момент $d p [i]$ містить суму найкоротших відстаней від вершини $i$ до всіх міст, у яких знаходяться гості. Залишається знайти мінімальне значення серед елементів масиву $d p$ і вивести відповідну відповідь. Змінна $pt r$ зберігає найменший номер вершини, у якій слід розмістити сервер.

res = INF;
for (i = 1; i <= n; i++)
{
  if (dp[i] < res)
  {
    res = dp[i];
    ptr = i;
  }
}

C++

Виводимо відповідь.

printf("%d %d\n", ptr, dp[ptr]);