Разъезд со стадиона
После матча машины выезжают с парковок у стадиона и разъезжаются по городу. Транспортная служба хочет знать, сколько потоков машин могут уезжать одновременно, если по каждой полосе идёт один поток: сколько полос в лучшем случае ведут от парковок к выездам из района. Полосы считаются по направлениям: у улицы может быть, например, две полосы в одну сторону и одна в другую, а у улицы с односторонним движением полос в обратную сторону нет вовсе.
Три теста — настоящие улицы центра Алматы из OpenStreetMap с числом полос в каждую сторону: парковки — все перекрёстки в 400 метрах от Центрального стадиона или в 500 метрах от Зелёного базара, выезды — все перекрёстки дальше трёх или двух с половиной километров от них.
Вход
В первой строке n и m (2 ≤ n ≤ 8000, 1 ≤ m ≤ 12 000) — число перекрёстков и кусков улиц. Дальше m строк a b f g: кусок улицы между перекрёстками a и b, по которому f полос ведут из a в b и g полос — из b в a (1 ≤ a, b ≤ n, a ≠ b, 0 ≤ f, g ≤ 10). Между одними и теми же перекрёстками может быть несколько кусков. Затем строка: k и k номеров перекрёстков у парковок; затем строка: l и l номеров перекрёстков-выездов. Эти наборы не пересекаются, k, l ≥ 1.
Выход
Одно число — наибольшее число полос, по которым потоки могут одновременно ехать от парковок к выездам: каждая полоса каждого куска улицы занята не больше чем одним потоком, и каждый поток — маршрут от какой-то парковки до какого-то выезда.
Примеры
Пример 1
6 7 1 2 3 0 1 3 2 0 2 4 2 0 2 5 2 0 3 4 3 0 4 6 2 0 5 6 3 0 1 1 1 6
4
Пример 2
7 7 1 3 2 2 2 3 1 1 3 4 1 0 3 5 2 1 4 6 2 2 5 7 1 1 5 4 1 1 2 1 2 2 6 7
3
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Это задача о максимальном потоке: пропускная способность дуги — число полос в эту сторону. Что делать, если истоков и стоков много?
2Подсказка 2
Первый пример: если пускать поток по найденным путям и никогда его не отменять, выйдет 3, а ответ 4. Какой путь нужно найти третьим?
3Идея
Добавим общий исток с дугами бесконечной ёмкости ко всем парковкам и общий сток с такими же дугами от всех выездов. Каждый кусок улицы даёт две дуги: a → b ёмкости f и b → a ёмкости g. Наибольший поток из общего истока в общий сток и есть ответ: по целочисленности поток раскладывается на маршруты по одной полосе.
4Разбор
Алгоритм Эдмондса — Карпа: поиском в ширину ищем путь по остаточной сети и пускаем по нему наименьший остаток. Каждую дугу добавляем парой с обратной, у которой ёмкость 0, — номера 2i и 2i + 1, тогда пара дуги a — это a ^ 1. Пустить x по дуге значит уменьшить её остаток на x и увеличить остаток пары на x.
Обратные дуги здесь обязательны. В первом примере после путей 1 → 2 → 4 → 6 (две полосы) и 1 → 2 → 5 → 6 (одна) свободных путей по самим улицам нет, но по остаточной сети есть путь 1 → 3 → 4 → 2 → 5 → 6: он идёт по дуге 4 → 2 против уже пущенного потока, отменяет одну полосу 2 → 4 и даёт четвёртую.
Несколько кусков улиц между одними и теми же перекрёстками ничему не мешают: это просто несколько дуг.
4+Решение
5Сложность
O(V E²) в худшем случае, но здесь путей не больше величины ответа, а он невелик: на настоящих улицах Алматы — 20 и 22 полосы. Каждый путь — один обход в ширину за O(V + E).
6Типичные ошибки
- Без обратных дуг. Жадный поток застревает — первый и седьмой тесты.
- Одна дуга на кусок улицы. Полосы в разные стороны — разные дуги; сложить их в одну неориентированную — значит разрешить ехать против одностороннего движения.
- Конечные ёмкости у общего истока. Если дать дуге к парковке ёмкость 1, ответ упрётся в число парковок.
- Нет пути вовсе. Ответ 0, восьмой тест.