Discussion @ 1421. Credit Operations @ Timus Online Judge

Idea?

Posted by Anton [SUrSU] 4 Feb 2007 18:40

Tell me pls the idea.

You need idea?

Posted by Alexander Kouprin 4 Feb 2007 20:26

Maxflow

Edited by author 25.10.2008 08:19

Re: You need idea?

Posted by svr 4 Feb 2007 21:56

O(n^3) MaxFlow, Cormen

Re: You need idea?

Posted by Anton [SUrSU] 5 Feb 2007 00:51

Maxflow... how? What network is here?

Re: You need idea?

Posted by svr 5 Feb 2007 07:54

n-sources- banks of 1-st policman
n- sinks- banks of second policemen
bipartite graf
capacities of sources and demands of sinks are given
flow must satisfiy them
add artificial one big source and one sink to make problem
classical. Use standard Maxflow algorithm-O(N^5) and you
will have TLE8. Replace standart (classical) algo by O(n^3) method from Cormen and you will have Ac.

Edited by author 05.02.2007 07:55

Re: You need idea?

Posted by Anton [SUrSU] 5 Feb 2007 12:36

Thanks!

Discussion of Problem 1421. Credit Operations