Енергетична мережа

Енергетична мережа складається з вузлів (електростанцій, споживачів та диспетчерів), з'єднаних лініями передачі електроенергії. Вузол $u$ може мати запас s(u) \geq 0 електроенергії, може виробляти кількість електроенергії 0 \leq p(u) \leq p_{\text{max}}(u), може споживати від $0$ до \min(s(u), c_{\text{max}}(u)) електроенергії, і передавати d(u) = s(u) + p(u) - c(u) електроенергії. Діють такі обмеження: c(u) = 0 для електростанцій, p(u) = 0 для споживачів, і p(u) = c(u) = 0 для диспетчерів. У мережі може бути не більше однієї лінії передачі $(u,v)$ від вузла $u$ до вузла $v$, яка передає від $0$ до l_{\text{max}}(u, v) електроенергії. Нехай Con = \sum_u c(u) — це загальна спожита електроенергія в мережі. Завдання полягає в обчисленні максимального значення $Con$.

На рисунку наведено приклад. Позначка $x/y$ для електростанції $u$ означає, що p(u) = x і p_{\text{max}}(u) = y. Для споживача $u$ позначка $x/y$ означає, що c(u) = x і c_{\text{max}}(u) = y. Для лінії передачі $(u,v)$ позначка $x/y$ означає, що l(u, v) = x і l_{\text{max}}(u, v) = y. Спожита електроенергія становить Con = 6. Зверніть увагу, що існують інші можливі стани мережі, але значення $Con$ не може перевищувати $6$.