I have directed graph (maybe with cycles), and some resources in vertices (let's say gold). I can transfer gold between vertices only in direction of edges. The task is to minimize maximum value of resources in vertices (e.g. make optimal redistribution of gold).

For example, enter image description here Optimal distribution for this graph is following:

6 => 5 => 5 => 5

So the answer is 6.

Or another example:

enter image description here

The answer is 9.

I think that solution should be based on finding max flow in graph and binary search for answer, but I can't connect these approaches and build proper solution. Could you please help?

  • $\begingroup$ Thanks for reply! In acyclic case should I make topological sort and check the possibility of collecting amount of gold less than given threshold t for every vertex in topological order? $\endgroup$
    – akarsakov
    Apr 4, 2019 at 20:30
  • $\begingroup$ Sorry, I found counterexample. Probably I'm missing something.. I'm still stuck on how to apply max flow algorithm even to acyclic graph case.. $\endgroup$
    – akarsakov
    Apr 4, 2019 at 21:43
  • $\begingroup$ Your inital idea of solving a kind of max-flow was good. You should find an elegant solution working on the Ford-Fulkerson algorithm. But I probably think to a different solution than D.W. $\endgroup$
    – Optidad
    Apr 5, 2019 at 14:07


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.