Discussion @ 1664. Pipeline Transportation @ Timus Online Judge

Which max flow algorithm must be used for acceptable perfomance?

Posted by indy256 20 Dec 2008 18:48

Re: Which max flow algorithm must be used for acceptable perfomance?

Posted by yzlhm 14 Mar 2010 13:49

dinic is all right

Re: Which max flow algorithm must be used for acceptable perfomance?

Posted by olpetOdessaONU [1 2/3] 9 May 2011 17:55

Does Dinic need some optimisation? It is O(n^2 * m) algorithm. This complexity is too large for 10^4 vertexes and 3*10^4 edges.

Re: Which max flow algorithm must be used for acceptable perfomance?

Posted by Marshall Mathers 27 May 2011 06:52

You should use as few variables as you can , in your dfs procedure. It does save time.
And you should 'delete' useless edges(which you've augmented it).
That's all measures I used in my dinic. And I got accepted within the limit.But still not too good.

Edited by author 27.05.2011 06:52

Discussion of Problem 1664. Pipeline Transportation