CS
Задачник Базовый курс EN

Задача

Кратчайшие маршруты без общих пересадок

потоки связность граф обход сети

Агентство продаёт групповые туры и предлагает только маршруты с наименьшим числом перелётов. Чтобы закрытие одного аэропорта не сорвало сразу несколько поездок, никакие две группы не должны пересаживаться в одном и том же аэропорту. Сколько групп можно отправить одновременно из s в t?

Маршрут — последовательность перелётов из s в t, и в нём ровно столько перелётов, сколько в самом коротком маршруте из s в t. Два маршрута не должны иметь общих аэропортов, кроме s и t. Если из s в t есть прямой рейс, кратчайший маршрут — только он, и ответ 1. Если долететь нельзя, ответ 0.

Тесты 5–7 — настоящая сеть рейсов всего мира: 3468 аэропортов и 84 869 направлений из базы позывных Virtual Radar Server. В седьмом тесте — маршруты из Алматы в пятьдесят аэропортов с наибольшим числом направлений.

Вход

В первой строке число аэропортов n и число направлений m (2 ≤ n ≤ 10⁴, 1 ≤ m ≤ 10⁵). Дальше m строк a b: есть перелёт из a в b (1 ≤ a, b ≤ n, a ≠ b, повторов нет). Затем число запросов q (1 ≤ q ≤ 50) и q строк s t (s ≠ t).

Выход

q строк: для каждого запроса — наибольшее число кратчайших маршрутов из s в t, никакие два из которых не проходят через общий аэропорт, кроме s и t.

Примеры

Пример 1

Вход
5 6
1 2
2 3
1 4
4 3
3 5
2 5
4
1 3
1 5
5 1
2 3
Выход
2
1
0
1

Пример 2

Вход
6 7
1 2
1 3
2 4
2 5
3 4
4 6
5 6
3
1 6
2 6
3 6
Выход
2
2
1

Ограничения

Время · Python
6500 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
11 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Какие перелёты вообще могут встретиться в кратчайшем маршруте? Посчитайте расстояние от s до каждого аэропорта и от каждого аэропорта до t — для второго нужен поиск в ширину по рейсам задом наперёд.

2Подсказка 2

Оставьте только такие перелёты и посмотрите на второй пример. Жадный проход «нашёл маршрут — закрыл его аэропорты — ищу следующий» находит 1 → 2 → 4 → 6, и маршрут через 3 упирается в занятый аэропорт 4. А ответ 2. Чего не хватает жадному проходу?

3Идея

Перелёт u → v лежит на кратчайшем маршруте, если ds(u) + 1 + dt(v) = ds(t). Только из таких перелётов строим сеть: каждый аэропорт, кроме s и t, — две вершины, прилёт и вылет, с дугой ёмкости 1 между ними, каждый перелёт — дуга ёмкости 1. Ответ — наибольший поток в этой сети. Любой путь из s в t по ней кратчайший, потому что каждая дуга ведёт на шаг дальше от s, а пути без общих вершин — это поток, в котором через каждый аэропорт идёт не больше единицы.

Жадный проход — это ровно одна фаза алгоритма Диница: блокирующий поток. Он не обязан быть наибольшим: в нём нельзя отменить уже пущенное. Наибольший поток получается, если продолжить фазы по остаточной сети, где у занятых перелётов и аэропортов появились обратные дуги. Во втором примере вторая фаза находит путь 1 → 3 → 4 → (назад) 2 → 5 → 6: маршрут через 2 отдаёт аэропорт 4 и уходит через 5.

4Разбор

Для каждого запроса: два поиска в ширину — от s по рейсам и от t по рейсам задом наперёд. Оставляем аэропорты с ds(v) + dt(v) = ds(t) и перелёты между ними, где ds растёт на единицу. Строим сеть с разрезанными аэропортами и запускаем Диница с указателями. Прямой рейс и недостижимая цель — отдельные случаи: 1 и 0.

Обратные дуги в остаточной сети ведут на слой назад, поэтому вторая и следующие фазы Диница ищут пути длиннее, чем первая. Но это пути по остаточной сети, а не маршруты: итоговый поток идёт только по дугам исходной сети, каждая из которых ведёт на шаг вперёд, и раскладывается на маршруты кратчайшей длины.

4+Решение
5Сложность

Сеть из разрезанных аэропортов единичная: в прилёт ведёт много дуг, но выходит одна, из вылета выходит много, но входит одна. По теореме о единичных сетях фаз не больше 2√V + 1, каждая за O(E), всего на запрос O(n + m) на поиски в ширину и O(E√V) на поток, где V и E — размер сети из кратчайших перелётов. На сети мира она обычно невелика; в восьмом тесте — 10 000 аэропортов в восьми слоях, и маршрутов там 1244.

6Типичные ошибки
  • Одна фаза. Жадный проход по слоям без обратных дуг — это wrong.py. На пятидесяти случайных парах аэропортов мира он ошибается дважды, на подобранных парах шестого теста — всегда, а в десятом тесте из полутора тысяч ловушек, как во втором примере, находит 1500 маршрутов вместо 3000.
  • Поток по всей сети. Если не отбрасывать перелёты вне кратчайших маршрутов, поток посчитает и маршруты длиннее. В первом примере из 1 в 5 кратчайший маршрут только 1 → 2 → 5, а с маршрутом 1 → 4 → 3 → 5 получилось бы 2.
  • Без разрезания аэропортов. Ёмкость 1 только на перелётах запрещает общие рейсы, но не общие аэропорты: два маршрута смогут прилететь в один аэропорт разными рейсами и улететь из него разными.

Алгоритмы задачи

GRA Алгоритм Алгоритм Диница Наибольший поток фазами: слоистая сеть, блокирующий поток, указатели; O(V²E), а в единичных сетях O(E√V). O(V² E) 2 задачи GRA Алгоритм Поиск в ширину Обходит граф слоями и находит пути с наименьшим числом рёбер за O(V + E). O(V + E) 2 задачи GRA Алгоритм Максимальный поток Наибольший поток из истока в сток и узкое место сети: Форд — Фалкерсон, Эдмондс — Карп, теорема о разрезе. O(V E²) 2 задачи
Каталог алгоритмов