Автор: | Южно-Уральский открытый командный чемпионат | Ограничение времени: | 5 сек | |
Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
Выходной файл: | output.txt |
Газовая компания должна поставлять потребителям определенный контрактами объем газа, но при транспортировке газ может откачиваться из трубы и в результате потребители могут не получить газ в нужном объеме.
Напишите программу, вычисляющую минимальный объем газа, который нужно поставлять газовой компании, чтобы всем потребителям газ дошел в объеме, определяемом контрактами.
Первая строка входного файла содержит три целых числа, разделенных пробелами — количество потребителей N, количество промежуточных насосных станций K и количество труб для транспортировки газа M.
Вторая строка содержит N целых чисел Vi, разделенных пробелами — объемы газа, которые необходимо поставить потребителям.
Далее следует M строк, содержащих по четыре целых числа, разделенных пробелами — номера узлов aj (0 ≤ aj ≤ K + N) и bj (0 ≤ bj ≤ K + N), связанных трубой, максимальный объем газа fj, который можно подать на вход этой трубы и процент газа dj, который выкачивается из этой трубы при транспортировке.
Узел c номером 0 соответствует компании-поставщику. Потребителям соответствуют узлы с номерами от 1 до N. Промежуточные насосные станции имеют номера от N + 1 до N + K. Между двумя узлами проходит не более одной трубы.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|