Заявки и мастера
В сервис ремонта в час пик приходят заявки. У каждой заявки свой список мастеров, которые умеют такую работу и успеют доехать; мастер за этот час берёт не больше одной заявки. Диспетчеру нужно назначить как можно больше заявок. Заявок бывает заметно больше, чем мастеров, и тогда часть заявок неизбежно ждёт следующего часа.
Данные выдуманы: генератор с фиксированным зерном.
Вход
В первой строке n и m (1 ≤ n, m ≤ 50 000) — число заявок и мастеров. Дальше n строк: число k и k различных номеров мастеров от 1 до m, которые подходят для заявки (0 ≤ k ≤ m). Сумма всех k не больше 150 000.
Выход
Наибольшее число заявок, которые можно назначить одновременно.
Примеры
Пример 1
4 3 2 1 2 1 1 2 2 3 1 3
3
Пример 2
5 4 2 1 2 1 1 1 2 2 1 2 2 3 4
3
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Это наибольшее паросочетание в двудольном графе «заявки — мастера». Почему жадное назначение — каждой заявке первого свободного мастера — ошибается на первом примере?
2Подсказка 2
Алгоритм Куна с новым поиском в глубину от каждой заявки верен. Сколько стоит поиск для заявки, которую назначить нельзя, и сколько таких заявок в третьем тесте?
3Идея
Нужен алгоритм Хопкрофта — Карпа. Неудачный поиск у Куна обходит всё, до чего дотягиваются чередующиеся пути от заявки, — часто почти весь граф, — и ничего не меняет. Когда мастеров вдвое меньше, чем заявок, неудачных поисков десятки тысяч, и время становится квадратичным. Хопкрофт — Карп за одну фазу обрабатывает все свободные заявки сразу: один обход в ширину строит слои, один проход в глубину по слоям находит много путей. Фаз немного — не больше примерно 2√V.
4Разбор
Фаза. Обход в ширину стартует сразу от всех свободных заявок: заявка → любой подходящий мастер → заявка, которая этого мастера сейчас держит, и так далее. Если по дороге встретился свободный мастер, увеличивающий путь есть, и расстояния до заявок — это слои. Затем от каждой свободной заявки ищем путь в глубину, но только из слоя d в слой d + 1. Найденный путь переворачиваем: каждая заявка на нём переходит к следующему мастеру, последний мастер был свободен. Вершину, из которой путь не нашёлся, помечаем тупиком до конца фазы — второй раз туда не зайдём, и вся фаза стоит O(E).
Почему фаз мало. После фазы кратчайший увеличивающий путь становится длиннее. После √V фаз все оставшиеся увеличивающие пути длиннее √V, а в разности текущего и наибольшего паросочетания они не пересекаются по вершинам, поэтому их не больше √V, — и каждая следующая фаза добавляет хотя бы один. Отсюда O(E √V).
Простое средство спасти Куна — не сбрасывать отметки после неудачного поиска — помогает лишь отчасти: после каждого удачного отметки всё равно сбрасываются, и замер в статье показывает, что на тех же данных он остаётся квадратичным.
4+Решение
5Сложность
O(E √V), где V = n + m, E — сумма длин списков. Кун — O(V E).
6Типичные ошибки
- Жадность. Первая заявка забирает мастера, без которого не обойтись второй, — первый пример.
- Кун «в лоб». Верно, но третий тест: 50 000 заявок на 25 000 мастеров, и почти каждый второй поиск неудачный.
- Рекурсия. Пути в чередующемся графе бывают длинными; на Python лучше свой стек.