Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

How to maximize flow while satisfying lower bounds on flow through individual edges ?

Правка en3, от Tanzir5, 2016-11-27 12:04:31

I was wondering if there is any way to solve the following problem:

" You are given a network graph. Every edge has two values associated with it: the upper bound of the amount of flow that CAN go through this edge and the lower bound of the amount of flow that MUST go through this edge. If there is no valid way to satisfy lower bound of all the edges, print "Unsolvable" . If there are multiple ways, maximize the amount of flow satisfying the lower bounds and upper bounds. You have to report the maximum amount and also the amount of flows through individual edges. "

I don't know of any online judge that has this problem. It's a random problem that came to my mind.

Теги maxflow, lower bound on maxflow

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Tanzir5 2016-11-27 12:04:31 57
en2 Английский Tanzir5 2016-11-25 11:30:13 419
en1 Английский Tanzir5 2016-11-25 11:20:43 1103 Initial revision (published)