Задачник Базовый курс EN

Снегоуборщик

граф кратчайший путь динамика битовые трюки карты и навигация логистика олимпиады

Ночью выпал снег. Снегоуборочная машина выезжает с перекрёстка-гаража, должна проехать по каждой улице своего района хотя бы раз и вернуться. Проезд по уже убранной улице — пустой пробег. Какой наименьший путь придётся проехать?

Улицы двусторонние, между двумя перекрёстками может быть несколько улиц, и по любой можно проезжать сколько угодно раз. С какого перекрёстка выезжает машина, на ответ не влияет: маршрут замкнутый. Тесты с пятого по седьмой — кварталы центра Алматы из статьи: квадраты вокруг площади Республики, театра оперы и балета и Зелёного базара, длины улиц — в метрах.

Вход

В первой строке n и m (2 ≤ n ≤ 5000, 1 ≤ m ≤ 10 000) — число перекрёстков и улиц. Дальше m строк a b w: улица длиной w метров между перекрёстками a и b (a ≠ b, 1 ≤ w ≤ 10 000). По улицам можно доехать от любого перекрёстка до любого. Перекрёстков, где сходится нечётное число улиц, не больше 22.

Выход

Одно число — длину самого короткого замкнутого маршрута, который проходит каждую улицу хотя бы раз.

Примеры

Пример 1

Вход

Выход

Пример 2

Вход

Выход

Ограничения

Время · Python: 6000 мс
Время · Go: 2000 мс
Память: 256 МБ
Проверка: 9 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Если у всех перекрёстков чётное число улиц, ответ — просто сумма длин: есть эйлеров цикл. Что мешает, когда нечётные перекрёстки есть?

2Подсказка 2

Посмотрите на улицы, которые маршрут проезжает второй (третий…) раз. У нечётного перекрёстка таких проездов нечётное число, у чётного — чётное. На что распадаются эти лишние проезды?

3Подсказка 3

Во втором примере нечётные перекрёстки 1, 2, 4 и 6. Самая близкая пара — 1 и 2, всего 2 метра. Что тогда останется на долю 4 и 6?

4Идея

Лишние проезды распадаются на пути между нечётными перекрёстками, по одному пути на пару, и, может быть, на циклы, которые маршрут не укорачивают. Значит, ответ — сумма длин всех улиц плюс наименьшая сумма кратчайших расстояний по разбиению нечётных перекрёстков на пары. И такой маршрут есть: если продублировать кратчайшие пути наилучшего разбиения, все степени станут чётными, и эйлеров цикл пройдёт каждую улицу (доказательство — в статье). Расстояния между нечётными перекрёстками даёт Дейкстра из каждого из них, а наилучшее разбиение на пары — динамика по маскам.

5Разбор

rest(mask) — наименьшая сумма для перекрёстков, которых нет в маске; самый младший свободный перекрёсток i спаривается первым, с каждым свободным j: rest(mask) = min(dist[i][j] + rest(mask ∪ {i, j})). Правило «младший первым» не теряет разбиений — i всё равно с кем-то в паре, — но и не перебирает одно разбиение в разных порядках. Масок 2²², а встречается при таком правиле меньше тридцати тысяч, поэтому удобна рекурсия с запоминанием в словаре.

Во втором примере сумма улиц 41. Жадный выбор берёт пару 1–2 за 2 метра, и на долю 4 и 6 остаётся 17: всего 19. Лучше пары 1–6 (6 метров) и 2–4 (9): 15, ответ 56. В квадрате вокруг площади Республики (пятый тест) жадность проигрывает 250 метров из 1690.

5+Решение

6Сложность

Дейкстра из каждого из k ≤ 22 нечётных перекрёстков — O(k · m log n), разбиение на пары — число встреченных масок, умноженное на k. Строить сам маршрут не нужно: хватит его длины.

7Типичные ошибки

Жадные пары. «Ближайшие сначала» проигрывает уже во втором примере: последние перекрёстки остаются далеко друг от друга.
Расстояние по прямой или одна улица. Вторая поездка идёт по улицам, и путь между парой — кратчайший путь в графе, а не ребро между ними.
Перебор всех масок подряд. Цикл по 2²² маскам с перебором пар в каждой — сотни миллионов шагов в Python; правило «младший первым» и запоминание оставляют только нужные состояния.

Алгоритмы задачи

GRA Алгоритм Эйлеров путь Пройти каждое ребро ровно раз: правило нечётных вершин и алгоритм Хирхольцера за O(E). O(V + E) 3 задачи GRA Алгоритм Алгоритм Дейкстры Кратчайшие пути от одной вершины во взвешенном графе без отрицательных рёбер. O((V + E) log V) 3 задачи DP Приём Динамика по маскам Состояние — подмножество, записанное битами числа: точный коммивояжёр, назначения, раскладки по профилю. O(2ⁿ · n²) для коммивояжёра 2 задачи