Никто не едет далеко
Снова n курьеров и n заказов с ценами — метрами пути по улицам, и каждый курьер берёт ровно один заказ. Но наименьшая сумма может отправить кого-то через весь город, а курьеры просят иначе: сначала пусть самая длинная поездка будет как можно короче, и только потом — как можно меньше сумма.
Найдите наименьшее возможное значение самой длинной поездки T, а среди распределений, где все поездки не длиннее T, — распределение с наименьшей суммой.
В двух тестах цены — расстояния по улицам Алматы до кафе из OpenStreetMap, как в статье.
Вход
В первой строке — n (1 ≤ n ≤ 100). Дальше n строк по n целых чисел от 0 до 109: цена пары «курьер i, заказ j».
Выход
В первой строке — T. Во второй — наименьшая сумма при поездках не длиннее T. В третьей — n чисел: номер заказа для курьеров 1, 2, …, n. Если подходящих распределений несколько, выведите любое.
Примеры
Пример 1
2 0 6 6 10
6 12 2 1
Пример 2
3 8 6 7 2 4 4 6 1 6
6 14 2 1 3
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Пусть порог T известен. Как проверить, можно ли распределить всех, используя только пары не длиннее T? Если можно при T, можно ли при большем?
2Подсказка 2
Когда наименьший порог найден, пары длиннее него запрещены. Как запретить пару венгерскому алгоритму, не меняя его?
3Идея
Сначала — двоичный поиск по порогу среди различных цен таблицы. Проверка порога — вопрос о совершенном паросочетании в двудольном графе, где остались пары не длиннее T; её решает алгоритм Хопкрофта — Карпа или обычный поиск увеличивающих путей из статьи о паросочетаниях. Если распределение есть при T, оно есть и при любом большем пороге, поэтому двоичный поиск законен.
Потом — венгерский алгоритм, где цена каждой пары длиннее T заменена очень большим числом, больше суммы любого распределения из разрешённых пар. Распределение из одних разрешённых пар существует, а любое распределение с запрещённой парой дороже его, так что ответ венгерского алгоритма запрещённых пар не содержит.
4Разбор
В первом примере наименьшая сумма — 0 + 10 = 10, но тогда второй курьер едет 10. Если первый возьмёт заказ 2, а второй заказ 1, обе поездки по 6: T = 6, сумма 12. Во втором примере есть два распределения с самой длинной поездкой 6 — с суммами 14 и 16, и нужно первое: заказы 2, 1, 3. Наименьшая сумма вообще, 10, потребовала бы поездку длиной 7.
Запрещённую цену удобно взять 1015: сумма разрешённых не больше 100 · 109.
4+Решение
5Сложность
Двоичный поиск — не больше log2(n2) ≈ 14 проверок. Хопкрофт — Карп — O(E√V), где E ≤ n2. Венгерский алгоритм — O(n3). Всё вместе при n = 100 — несколько миллионов действий.
6Типичные ошибки
- Только наименьшая сумма. Венгерский алгоритм сам по себе на длинную поездку не смотрит — первый пример.
- Только порог. Найти T мало: среди распределений с поездками не длиннее T суммы разные — второй пример.
- Жадный выбор по порогу. «Каждому курьеру — ближайший свободный заказ не длиннее T» может зайти в тупик там, где распределение есть: нужно именно паросочетание.
- Запрещённая цена мала. Если она меньше суммы, которую может набрать распределение, венгерский алгоритм иногда выберет запрещённую пару.