Discussion @ 1421. Credit Operations @ Timus Online Judge

O(V^2*E) passes TL! (+)

Posted by Vedernikoff Sergey (HSE: EconomicsForever!) 22 Jul 2008 00:43

Usual generic preflow algo got AC in 0.093 sec. Maybe, it worth to decrease timelimit?

Re: O(V^2*E) passes TL! (+)

Posted by Chmel_Tolstiy 22 Jul 2008 01:05

I think it is a bad idea. BS Flow by dfs not works. So it's very nice problem.

Re: O(V^2*E) passes TL! (+)

Posted by maksay 17 Mar 2009 21:53

Even simple bfs & dfs combination gets AC in 0.187=) (using scaling, of course). And its' complexity is higher than O(V^2*E).I think, it is closer to (E^2*logU)

Re: O(V^2*E) passes TL! (+)

Posted by Ripatti [Ufa] 26 Nov 2010 12:03

Dfs works. I got AC with 0.21 sec by using some tricky dfs with scalling.

Re: O(V^2*E) passes TL! (+)

Posted by Strekalovsky Oleg [Vologda SPU] 17 Jun 2011 12:34

Simple preflow push algo O(N^2*E) passed on Java in 0.14.

Discussion of Problem 1421. Credit Operations