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

Mincost maxflow special case
Автор I_love_Hoang_Yen, 10 лет назад, По-английски

Given a Mincost Maxflow problem where all costs are non-negative integers at most K, for some small values of K (K = 1, 2, 3...)

I've heard the following claim: There is ALWAYS a conversion from this Mincost Maxflow problem to a Maxflow problem. Is this claim true? If yes, then I think it is very valuable in competitions.

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

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

Well if K is small then you can generally profit by finding a shortest path in a graph in O(V + E + K). While this isn't a reduction to MaxFlow, it does bring your time complexity to something similar.

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

    How? Oo

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

      Split each edge into Ki edges with cost 1 and run bfs.

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

        It is O(V + E * K), isn't it? Also what to do on next iterations?..

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

          Edit: wrong, of course

          Something like O( K). Not sure if I understand your question. You do the same thing on each iteration, just as you would in Min-Cost Flow with Bellman-Ford or with Dijkstra + potentials.

          In the end, each part of the initially divided edge will be filled with the same amount of flow, so it will be easy to get back to the original graph.

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

            klamathix saying about O(V + E + K), but your solution is O(V + E * K). Actually we can make first iteration in with a simple Dijkstra in this case, so...

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

        And then in residual graph we will have edges with -1 cost , how can you run BFS in this case?

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

    I see. But there are many Max flow algorithm that is not based on finding augmenting path and are much faster, so even with this trick, Min cost is still much slower.

    UPD: and as mentioned, in residual graph, there are negative edges. How to deal with that? :)

    → Ответить