План перевозок
Есть k источников груза и d станций. В источнике i лежит ai единиц, станции j нужно bj, и всего лежит ровно столько, сколько нужно. Возить можно только по m путям из таблицы; путь из источника i на станцию j стоит c за единицу и пропускает сколько угодно. Развезите весь груз так, чтобы суммарная стоимость была наименьшей.
Третий тест — задача А. Н. Толстого 1930 года: 10 источников, 68 станций и 155 путей с расстояниями в километрах по таблице, которую перепечатал Александр Схрейвер; груз — в сотнях тонн.
Вход
В первой строке k, d и m (1 ≤ k ≤ 60, 1 ≤ d ≤ 600, 1 ≤ m ≤ 6000). Во второй — k чисел ai, в третьей — d чисел bj (от 1 до 10⁵, сумма тех и других одна и та же и не больше 10⁶). Дальше m строк i j c: путь из источника i на станцию j стоимостью c за единицу (0 ≤ c ≤ 10⁴). Пара i, j встречается не больше одного раза, и развезти весь груз по этим путям можно.
Выход
Наименьшая суммарная стоимость. Она может не поместиться в 32 бита.
Примеры
Пример 1
2 3 5 3 2 2 2 1 1 1 4 1 2 6 2 2 3 2 3 5 1 3 9
22
Пример 2
2 2 3 1 1 1 1 1 1 1 1 2 2 2 1 3
5
Ограничения
- Время · Python
- 14000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Самый дешёвый путь — в первую очередь? Посмотрите на второй пример: дешёвый путь из первого источника на первую станцию забирает у второй станции её единственный источник. Как исправить уже сделанную перевозку?
2Подсказка 2
Постройте сеть: исток → источники (ёмкость ai) → станции (пути из таблицы, стоимость c) → сток (ёмкость bj). Нужен поток величины Σbj наименьшей стоимости. Что должна стоить обратная дуга?
3Идея
Это поток наименьшей стоимости. Обратная дуга стоит минус стоимость прямой — отменить перевозку значит сэкономить её цену. Растим поток с нуля, каждый раз по самому дешёвому пути от истока к стоку в остаточной сети. По теореме о последовательных кратчайших путях в остаточной сети никогда не появляется отрицательного круга, а значит, каждый промежуточный поток наилучший для своей величины, и последний — тоже.
4Разбор
Дуги храним парами: a и a ^ 1, у обратной ёмкость 0 и стоимость −c. Пути от источника к станции даём ёмкость «сколько угодно» — хватит суммы всех потребностей. Кратчайший путь ищем Дейкстрой по приведённым стоимостям c + π(u) − π(v); после поиска прибавляем расстояния к потенциалам. Начальные потенциалы — нули: все стоимости неотрицательны. По найденному пути пускаем столько, сколько позволяет самая узкая дуга, и прибавляем к ответу количество × (π(t) − π(s)) — после обновления это и есть стоимость пути в настоящих ценах.
В тесте Толстого выходит 3 950 520 сотен тонно-километров, то есть 395 052 тысячи — столько же, сколько у его плана.
4+Решение
5Сложность
Каждый путь насыщает дугу источника, дугу станции или отменяет перевозку. На этих тестах путей самое большее в полтора раза больше, чем источников и станций вместе: в задаче Толстого 89 при 78, в шестом тесте 933 при 610. Каждый поиск — O(E log V). Беллман — Форд с очередью вместо Дейкстры здесь тоже проходит: в такой сети почти нет кругов, как показывает замер в статье.
6Типичные ошибки
- Самый дешёвый путь из таблицы в первую очередь — «метод наименьшего элемента». Это
wrong.py: без отмен он то переплачивает, как в первом примере (23 вместо 22), то застревает, когда у станции не осталось источников, как во втором. В задаче Толстого он так оставляет без груза шесть станций. - Дейкстра без потенциалов. После первой отмены в остаточной сети есть дуги отрицательной стоимости, и Дейкстра по настоящим ценам может ошибиться.
- 32 бита. Груза до миллиона, цена до десяти тысяч — сумма может дойти до 10¹⁰.
Алгоритмы задачи
O(F · E log V)
2 задачи
GRA
Алгоритм
Алгоритм Дейкстры
Кратчайшие пути от одной вершины во взвешенном графе без отрицательных рёбер.
O((V + E) log V)
3 задачи