For the past few weeks I've been trying to code an algorithm for the Mincost Maxflow problem, but I've had a lot of problems. I see this problem as been very interesting, as there are a lot of problems that can be solved by it (10594, 2691, 10888, 10746 come to mind). I was hoping you could help me. Here's the deal:

1. I've coded the Min Mean Cycle Canceling algorithm, only later to realize his time complexity is O(n^2*m^3*log n) which is, obviously, pretty huge. My algorithm seems to be ok, but I can't get past TLE in any of those problems I mentioned earlier.

2. I'm not sure even which algorithm I should code. I've encountered references to some algorithms: Min Mean Cycle Canceling, Cost Scaling and Sucessive Shortest Paths. The best among these seems to be the "Cost Scaling", which I think has complexity O(n^2*m*log (nC)) - where C is an upper bound on the edges cost.

I have two problems: first of all, I can't find any good material on these algorithms. Googling only got me some .ppts and very general description of them. Does anybody have a good text on any of these? My second issue is that even the "best" one of the mentioned algorithms has a "big" time complexity: for instance on problem 10594 n=100 and m=5000, so we have O(100*100*5000*log (100*C)), and that is a very big time complexity.

If someone could help, comment or point me in the right direction I would

**really**appreciate.