mylyanyk.ivan's blog

[need help] Min Cost Max Flow faster implementation
By mylyanyk.ivan, 11 years ago, translation, In English

Hi guys,

I was looking for min-cost-max-flow problems and found this

http://www.spoj.com/problems/GREED/

I coded solution, submitted it and received AC with about 20s time. Unfortunately, there are accepted runs with time less than 2s.

I guess my solution in so slow because of my poor implementation of the algorithm.

Can somebody take a look on my solution and tell me what I'm doing wrong?

my solution

UPD: I've implemented Dijkstra's algo with potentials, and ... accepted this problem with 40s. Twice slower! I don't know, what's wrong with me? :/

My new solution with Dijkstra

UPD2: Changed algorithm to use Dijkstra for sparse graph. However, received AC with ~40s. OMG, WHAT IS WRONG WITH MY CODE?

Algo using Dijkstra for sparse graphs

Thanks in advance.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

As Burunduk1 explained, if you solve the assignment problem using ordinary min-cost-max-flow with Bellman-Ford (as you do), your solution can easily degrade to O(N^4). The bad test case is a multiplication table as the matrix of weights.

So, you should use Dijkstra's algorithm with potentials for finding the shortest path. Information about it is available online, I can remember one very short Russian article about it — using that idea you'll get an O(VE * log V) or O(V^3) algo for the assignment problem.

Also, you can try to use the Hungarian algorithm.

UPD. Yes, in this problem it's impossible to build such a weight matrix, but anyway, Dijkstra with potentials is noticeably faster than Bellman-Ford with a queue.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, thanks for your comment!

    I've implemented Dijkstra's algo with potentials, and ... accepted this problem with 40s. Twice slower. I don't know, what's wrong with me? :/

    My solution with Dijkstra

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      And how does SPOJ measure the performance of the solution? Does it measure the total time or maximal time for a testcase? If first, O(N^2) Dijkstra implementation's slow performance on sparse graphs will add a lot into your running time...

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        As far as I know and checked on their forum — they measure a total time.

        OK, I'll try again :) Thanks for support :)

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Also, there exists an unproven hypothesis that (if correct) allows the implementation of shortest path search in O(V + E).

          The hypothesis itself: if you search the min-cost-max-flow in a 0-1 graph (I mean: graph with edges of only zero and one initial weight), there won't appear any edges of greater weight thereafter (if you'll use potentials, of course).

          In such a case you'll be able to get rid of the priority queue and use a deque instead of it (if you don't know: after relaxing a vertex via a zero edge, you need to add it to the beginning of the deque, and to the end otherwise).

          The hypothesis is mine, but to surely use it, you need to prove it.

          → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Made some updates:

        UPD2: Changed algorithm to use Dijkstra for sparse graph. However, received AC with ~40s. OMG, WHAT IS WRONG WITH MY CODE?

        Algo using Dijkstra for sparse graphs

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          ← Rev. 2   Vote: I like it +5 Vote: I do not like it

          I think, if you want less time — use priority_queue instead of set, or furthermore use your own heap. Also, as AlexanderBolshakov said, you can use 0-k BFS in O(V + E).

          → Reply
»
11 years ago, # |
  Vote: I like it -11 Vote: I do not like it

http://tny.cz/c0aadc2a

→ Reply