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

Idea?

Послано Anton [SUrSU] 4 фев 2007 18:40

Tell me pls the idea.

You need idea?

Послано Alexander Kouprin 4 фев 2007 20:26

Maxflow

Edited by author 25.10.2008 08:19

Re: You need idea?

Послано svr 4 фев 2007 21:56

O(n^3) MaxFlow, Cormen

Re: You need idea?

Послано Anton [SUrSU] 5 фев 2007 00:51

Maxflow... how? What network is here?

Re: You need idea?

Послано svr 5 фев 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?

Послано Anton [SUrSU] 5 фев 2007 12:36

Thanks!

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