Обсуждение @ 1421. Кредитные операции @ Timus Online Judge

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

Послано Vedernikoff Sergey (HSE: EconomicsForever!) 22 июл 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! (+)

Послано Chmel_Tolstiy 22 июл 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! (+)

Послано maksay 17 мар 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! (+)

Послано Ripatti [Ufa] 26 ноя 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! (+)

Послано Strekalovsky Oleg [Vologda SPU] 17 июн 2011 12:34

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

Обсуждение задачи 1421. Кредитные операции