Блог пользователя game_changer007

Автор game_changer007, история, 10 лет назад, По-английски

Hi,I am trying to solve this problem on Spoj.

I have implemented simple Dinic's algorithm only,but am getting TLE.Here is the solution link solution .Am I doing anything wrong?

Please help!!

Edit:Got AC!!

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

In your dfs function you are unnecessarily iterating over the used edges. You only need to start from scratch whenever you recompute the bfs function(), and not everytime.

In short

1)Make a ptr[] array (size >= number of vertices)

2)change line 75 to for(;ptr[u]<g[u].size();++ptr[u]) //ptr[u] stores your position in g[u]

3)Do a memset(ptr,0,sizeof ptr) after your bfs function returns true

http://e-maxx.ru/algo/dinic

»
10 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Another way of changing it is just adding something like d[u] = 1000000000ll before return 0 in the dfs.

Here is an accepted solution of your code: http://ideone.com/LBl7V9