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?
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? :/
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.
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.
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
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...
As far as I know and checked on their forum — they measure a total time.
OK, I'll try again :) Thanks for support :)
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.
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
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).
http://tny.cz/c0aadc2a