Блог пользователя rumman_sust

Flow
Автор rumman_sust, 10 лет назад, По-английски

How can I find the minimum cost max-flow in a graph where the capacity of an edge have a lower and upper bound (UPD: Edge have a capacity within a range [l,r])?

UPD: FLOW (not capacity) of an edge have a lower and upper bound

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What do you mean by lower and upper bound? If you mean that the capacity of the edge must always be within a range [l,r], then just set its capacity to r-l and do a normal flow algorithm.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes the capacity of an edge is within a range [l,r]. But your idea is not right. See this graph,

    1-->2(l=5,r=10,cost=2)

    2-->3(l=9,r=14,cost=2)

    Where source is 1 and sink is 3.

    Here, the maximum flow is 10 and the cost is 20. But according to your idea the maximum flow is 5 and the cost is 10. Correct me if I'm wrong.

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      if I remember correctly the lower-bound max flow can be translated into a max-flow without lower-bounds but I'm not sure if it can be applied to costed max flow

      → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      If the CAPACITY of the edges has to be in the ranges [5,10] and [9,14], then the answer is 5. You send 5 units of flow through the path, the capacity of the first edge decreases to 5 and the capacity of the second edge decreases to 9. No further flow can be sent.

      If, on the other hand, the FLOW that goes through the edges has to be in the ranges [5,10] and [9,14], then that's a completely different problem and the solution I suggested wouldn't work. If that's what you're actually asking, you should rephrase your post.

      → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It was my fault. Sorry for the inconvenience. updated the post. Thanks for pointing out my mistake.

        → Ответить