ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1774. Barber of the Army of Mages

Ford-Fulkerson tl22
Posted by Ibragim Atadjanov (Tashkent U of IT) 23 Oct 2010 19:59
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
Posted by Ibragim Atadjanov (Tashkent U of IT) 24 Oct 2010 05:01
Re: Ford-Fulkerson tl22
Posted by Ibragim Atadjanov (Tashkent U of IT) 24 Oct 2010 05:01
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
Posted by Ibragim Atadjanov (Tashkent U of IT) 27 Oct 2010 02:19
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
Posted by Halilc4 5 Apr 2011 13:44
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
Posted by Milanka Halilovich 8 Apr 2011 07:06

Edited by author 08.04.2011 18:48
Re: Ford-Fulkerson tl22
Posted by Kolyanich 6 Jul 2011 23:13
My simple BFS implementation of F-F also TLed, but Dinic's modification got AC
Re: Ford-Fulkerson tl22
Posted by waterlink 20 Aug 2011 04:53
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
Posted by die_young 20 Jul 2018 22:31
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.