Обсуждение @ 1664. Нефтепроводы @ Timus Online Judge

Which max flow algorithm must be used for acceptable perfomance?

Послано indy256 20 дек 2008 18:48

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

Послано yzlhm 14 мар 2010 13:49

dinic is all right

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

Послано olpetOdessaONU [1 2/3] 9 май 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?

Послано Marshall Mathers 27 май 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

Обсуждение задачи 1664. Нефтепроводы