I've used Ford-Fulkerson algo and got TL on test 22.(in java)

I took in internet one of the  best Ford-Falkerson with BFS, based on
priority queue and got Ac immidiately(but time is not very good)

Could you give me the link to this site please

Could you give me the link to this site please

TLE? It's really strange. Try to find bug in your code. I accepted this problem using usual Ford-Fulkerson at 0.031
May be the reason of TLE is realization of algo. Or possibly you build graph in some strange manner.
Don't use adjacency matrix. Just use list of edges for each vertices.
Build bipartite graph. Left part is mages (100 vertices). Right part - is time at which mages would be possibly shave (2000 vertices). Connect i-th mage with ti...ti+si-1 times (1-capacity).
Connect source vertex with each mage (2-capacity). Connect each time (0..2000) with target vertex (k-capacity).

I'd built the graph as you said. I didn't use adjacency matrix instead I used adjacency list for each vertex. I don't know what to do else.

i saw that you had WA on 39. test... i have same problem... if you could say to me what have you done to get AC?

there are some anti-bfs tests, try to cheat somehow :)

Edited by author 08.04.2011 18:48

My simple BFS implementation of F-F also TLed, but Dinic's modification got AC

ford-fulkerson based on simple dfs gives ac in 0.031
let us calc complexity, O(E * F), where E is edge's count, F is flow
in huge test E is ~ 2000 * 100 + 2000 + 100
F is ~ 200
so we have ~ 40*10^6 operations multiplied by some constant
if use own vectors (not stl-one), based on simple arrays, you'll be ok
this problem does not need bfs-flow, 'cause there are 1-weighted edges on the way every time

Edited by author 20.08.2011 04:55

Edited by author 12.07.2012 19:25

If you FF algorithm runs slow you can add scaling, either bit-scaling or simple capacity scaling, this alone should be enough to deal with all possible anti-FF networks.