Каскад Токтогульской ГЭС


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Токтогульское водохранилище на реке Нарын — крупнейшее в Центральной Азии. Из него вода идёт через каскад гидроэлектростанций и сеть каналов к полям Ферганской долины.

Фотография
Токтогульское водохранилище. Фото: Benjamin Goetzinger, CC BY-SA 4.0, Wikimedia Commons

Инженер Талант моделирует распределение воды на сутки. Сеть состоит из n узлов (водохранилище — узел 1, главный распределительный узел в долине — узел n) и m каналов. Канал j ведёт воду только в одном направлении — из узла u[j] в узел v[j]. Через него нужно пропустить целое количество x[j] кубометров воды, причём

l[j] ≤ x[j] ≤ c[j],

где c[j] — пропускная способность канала, а l[j] — экологический минимум: меньше этого количества пропускать нельзя, иначе пересохнет русло и погибнет рыба. Перекачка одного кубометра по каналу j стоит w[j] сомов.

В каждом промежуточном узле (кроме 1 и n) сколько воды втекает, столько и вытекает. Из узла 1 должно вытечь (с учётом воды, которая в него возвращается по каналам) ровно F кубометров, и ровно столько же должно поступить в узел n.

Найдите минимальную суммарную стоимость такого распределения или выведите -1, если выполнить все требования невозможно.

Рисунок

Входные данные

В первой строке — три целых числа n, m, F (2 ≤ n ≤ 200, 1 ≤ m ≤ 3000, 0 ≤ F ≤ 10⁹).

В каждой из следующих m строк — пять целых чисел u[j], v[j], l[j], c[j], w[j] (1 ≤ u[j], v[j] ≤ n, u[j] ≠ v[j], 0 ≤ l[j] ≤ c[j] ≤ 10⁹, 0 ≤ w[j] ≤ 1000). Между двумя узлами может быть несколько каналов, в том числе встречных.

Выходные данные

Выведите одно целое число — минимальную стоимость или -1.

Пример 1

Вход:

4 5 6
1 2 0 5 1
1 3 2 4 3
2 4 0 4 2
3 4 0 6 1
2 3 0 3 1

Выход:

20

Пример 2

Вход:

4 5 10
1 2 0 5 1
1 3 2 4 3
2 4 0 4 2
3 4 0 6 1
2 3 0 3 1

Выход:

-1

Пояснение

В первом примере по каналу 1 → 3 нужно пустить не меньше 2 кубометров (стоимость пути 1 → 3 → 4 — 4 сома за кубометр). Остальные 4 кубометра выгоднее пустить по пути 1 → 2 → 4 за 3 сома: всего 2 · 4 + 4 · 3 = 20.

Во втором примере из узла 1 можно выпустить не более 5 + 4 = 9 кубометров.

Система оценивания

Подзадача Баллы Дополнительные ограничения
1 10 n ≤ 5, m ≤ 7, c[j] ≤ 3
2 25 все l[j] = 0
3 20 n ≤ 50, m ≤ 500
4 45 без дополнительных ограничений

Баллы за подзадачу начисляются, только если пройдены все её тесты.


Комментарии

Еще нет ни одного комментария.