Ford-Fulkerson tl22

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

Re: Ford-Fulkerson tl22

Posted by

svr 23 Oct 2010 20:40

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)

Re: Ford-Fulkerson tl22

Could you give me the link to this site please

Re: Ford-Fulkerson tl22

Could you give me the link to this site please

It's strange

Posted by

vgu 25 Oct 2010 01:59

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).

Re: It's strange

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.

Re: It's strange

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?

Re: Ford-Fulkerson tl22

Posted by

KALO 7 Apr 2011 03:58

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

No subject

*Edited by author 08.04.2011 18:48*

Re: Ford-Fulkerson tl22

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

Re: Ford-Fulkerson tl22

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*

Re: Ford-Fulkerson tl22

Posted by

Viktor 12 Jul 2012 14:40

*Edited by author 12.07.2012 19:25*

Re: Ford-Fulkerson tl22

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.