Маршруты без общих перекрёстков
Служба охраны готовит проезд кортежа из одного перекрёстка города в другой. Чтобы одна авария или одно перекрытие не сорвали всё, она хочет заранее подготовить как можно больше запасных маршрутов, и никакие два маршрута не должны проходить через один и тот же перекрёсток — кроме, конечно, начала и конца. Сколько таких маршрутов можно подготовить?
Три теста — настоящие улицы центра Алматы из OpenStreetMap, все улицы двусторонние; начало и конец — ближайшие к ориентирам перекрёстки, где сходятся хотя бы три улицы.
Вход
В первой строке n, m, s и t (2 ≤ n ≤ 10 000, 0 ≤ m ≤ 25 000, 1 ≤ s, t ≤ n, s ≠ t) — число перекрёстков, число улиц, начало и конец. Дальше m строк a b: улица между перекрёстками a и b, по ней можно ехать в обе стороны. Улица не соединяет перекрёсток сам с собой, и между двумя перекрёстками не больше одной улицы.
Выход
Наибольшее число маршрутов из s в t, никакие два из которых не проходят через общий перекрёсток, кроме s и t. Улица прямо из s в t, если она есть, — тоже маршрут.
Примеры
Пример 1
8 8 1 8 1 2 1 3 2 4 3 4 4 5 4 6 5 8 6 8
1
Пример 2
7 10 1 7 1 2 2 7 1 3 3 4 4 7 1 7 3 5 5 6 6 7 2 4
3
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Если бы маршрутам запрещалось только делить улицы, хватило бы потока с ёмкостью 1 на каждой улице. Почему в первом примере такой поток даёт 2, а ответ 1?
2Подсказка 2
Ограничение нужно поставить на перекрёсток, а поток умеет ограничивать только рёбра. Как превратить вершину в ребро?
3Идея
Разрежем каждый перекрёсток v на две вершины: вход vin и выход vout, соединённые дугой ёмкости 1. Улица a — b превращается в дуги aout → bin и bout → ain. Теперь через перекрёсток проходит не больше одной единицы потока, и наибольший поток из sout в tin — это число маршрутов без общих перекрёстков.
4Разбор
Почему поток равен ответу. Любой набор маршрутов без общих перекрёстков даёт поток той же величины: по каждому маршруту пустим единицу, и ни одна дуга «вход → выход» не получит больше одной. Обратно: ёмкости целые, поэтому найдётся наибольший поток из нулей и единиц, а такой поток раскладывается на пути из s в t. Два пути не могут пройти через один перекрёсток, потому что дуга vin → vout пропускает одну единицу. Начало и конец не разрезаем — у них ограничения нет, — или, что то же, даём их дугам большую ёмкость.
Поток ищем Эдмондсом — Карпом: каждый путь прибавляет единицу, и путей не больше степени s. Ответ ещё и равен наименьшему числу перекрёстков, после закрытия которых из s в t не проехать, — это теорема Менгера. На настоящих улицах Алматы в двух тестах ответ 3, а к Кок-Тобе ведёт один маршрут: на нём есть перекрёсток, через который проходят все пути.
Если два маршрута встречаются на перекрёстке, но приходят и уходят по разным улицам, подсчёт без разрезания вершин засчитает оба. Седьмой тест построен так: сорок цепочек, и каждые две встречаются в общей средней точке — маршрутов без общих улиц 40, без общих перекрёстков 20.
4+Решение
5Сложность
Вершин 2n, дуг (с обратными) 2n + 4m. Каждый обход в ширину — O(n + m), обходов — не больше ответа плюс один, а ответ не больше степени s. Итого O(deg(s) · (n + m)).
6Типичные ошибки
- Не разрезать вершины. Получится число маршрутов без общих улиц — первый и седьмой тесты.
- Разрезать начало и конец с ёмкостью 1. Тогда ответ всегда не больше одного.
- Улица — одна дуга. Улицы двусторонние, нужны дуги в обе стороны.
- Нет пути. Ответ 0, девятый тест.