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

Maximum flow problem
Автор notking, история, 7 лет назад, По-английски

How can I solve the maximum flow problem when the capacity is not on the edge but only on the vertices? There are no multiple edges. Can I remove capacity from vertices and for each edge put its capacity equal to the minimum of capacities of 2 vertices it connects and then apply the maximum flow algorithm? Will this work?

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

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

Put Infinite capacity on edges. Then, for each vertice v, add a vertice v' and an edge from v to v' with the capacity of v.

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

    For each vertex, we make an auxiliary vertex and connect it to the main vertex with the capacity of the main vertex. Now, when we will run the maximum flow, the answer would be infinite no?

    Also, what's wrong with my approach?

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

      Maybe you understood it wrong: you make v', connect it to v with capacity c[v] (edge is directed from v to v'), and then every edge that was ended in v still ends in v, but edge which started from v now starts from v'. That way you can guarantee that through v goes not more than c[v] of flow.

      And, no, ofcourse answer will be less than infinity for the obvious reasons.

      P.S. Maybe your approach is correct, but the main way of solving such problems is to try to build equivalent graph so the max flow will be the same for it, and you are trying something a little different.

      → Ответить