sherewillpower's blog

By sherewillpower, history, 7 years ago, In English

I am trying to learn Dinic's algorithm to find max flow for a given graph. However my implementation for the same is timing out for the 11th pretest for the question FASTFLOW on SPOJ whatever I do. It's been a day and I haven't been able to find the fault. Please can anyone help me optimize my code further?

Link to question : http://www.spoj.com/problems/FASTFLOW/

My code: http://ideone.com/7FFYRy

Any help would be appreciated, Thank you.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Use adjacency list instead of adjacency matrix. This is because every operation even bfs runs with O(V2) and same goes for the dfs.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, I am using an adjacency list(graph) for bfs and dfs. My matrices flow and capacity are just there to store the present values, but the traversal is being done on the adjacency list

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      I found your mistake. You are actually not implementing dinic's. Your algorithm is just a modified Edmond's Karp. After a bfs you're not augmenting all the paths from source to sink. Instead you're augmenting just one path in the level graph and running the bfs again which is wrong. What you have to do is keep on running the dinic's function as long as dinic(source, sink, LONG_LONG_MAX)! = 0 for the level graph which implies that you've done augmenting all the paths in the level graph. Also, the implementation that you've done is highly memory inefficient. If the number of nodes increases the matrix of flow and capacity will go out of memory. Use a better implementation where we make a struct of edges and stores the adjacent indexes.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks a lot! Got AC! I was actually running the Dinics function until one vertex was done with, however I had to change my code numerous times due to the persisting TLE. Forgot to add it back

        This is my AC code: http://ideone.com/J4BASW