Курьеры и заказы
В городе n свободных курьеров и n готовых заказов. Для каждой пары известна цена — сколько метров курьеру ехать по улицам до заказа. Каждый курьер берёт ровно один заказ, каждый заказ достаётся ровно одному курьеру. Распределите заказы так, чтобы сумма цен была наименьшей.
В двух тестах цены — настоящие расстояния по улицам Алматы от случайных перекрёстков до кафе из OpenStreetMap, как в статье; в остальных — случайные и нарочно неудобные таблицы.
Вход
В первой строке — n (1 ≤ n ≤ 150). Дальше n строк по n целых чисел: в строке i на месте j — цена пары «курьер i, заказ j», от 0 до 109.
Выход
В первой строке — наименьшая сумма. Во второй — n чисел: номер заказа для курьеров 1, 2, …, n. Если лучших распределений несколько, выведите любое.
Примеры
Пример 1
3 1 2 9 2 9 9 9 9 3
7 2 1 3
Пример 2
4 4 4 4 4 4 4 4 4 1 4 4 4 4 4 4 1
10 3 2 1 4
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Возьмите в первом примере самую короткую пару, потом самую короткую из оставшихся, и так далее. Сколько получилось? Можно ли меньше?
2Подсказка 2
Подберите каждому курьеру и каждому заказу по числу так, чтобы у любой пары сумма двух чисел не превышала цены. Почему тогда никакое распределение не стоит меньше суммы всех этих чисел? Что, если распределение использует только пары, где сумма равна цене?
3Идея
Венгерский алгоритм из статьи. Потенциалы ui курьеров и vj заказов всё время удовлетворяют ui + vj ≤ cij, а распределение строится только по честным парам, где это равенство. Курьеры добавляются по одному: от нового курьера растёт дерево по честным парам через занятые заказы; когда честных пар не хватает, потенциалы курьеров дерева растут на δ — наименьшую приведённую цену из дерева наружу, — а заказов дерева уменьшаются на δ. Появляется новая честная пара, прежние не портятся. Как только в дереве оказался свободный заказ, путь до него переворачивается. В конце все пары честные, и по теореме из статьи сумма наименьшая.
4Разбор
Короткая запись с фиктивным столбцом 0 и массивами minv (наименьшая приведённая цена до каждого заказа вне дерева) и way (откуда к нему пришли) — та же, что в листинге статьи. В первом примере жадность берёт пару (1, 1) за 1, потом (3, 3) за 3 и вынуждена отдать курьеру 2 заказ 2 за 9: всего 13. Лучшее — 2 + 2 + 3 = 7: курьер 1 берёт заказ 2, курьер 2 — заказ 1.
Суммы доходят до 150 · 109: в Go нужен int64.
4+Решение
5Сложность
O(n3): для каждого из n курьеров не больше n сдвигов потенциалов по O(n). При n = 150 это около трёх миллионов простых действий.
6Типичные ошибки
- Самая короткая пара первой. Последним курьерам остаются дорогие заказы — первый пример.
- Каждому заказу — ближайший свободный курьер. Та же ошибка с другой стороны.
- Перебор перестановок. 150! вариантов — даже при n = 12 это уже полмиллиарда.
- Бесконечность на пределе типа. Если в Go взять за «бесконечность»
math.MaxInt64, вычитание δ из неё и сложение с потенциалами переполняются; хватитmath.MaxInt64 / 4. В Python подходитfloat('inf'): вычитание δ её не портит, а сами потенциалы остаются целыми.