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.
Use adjacency list instead of adjacency matrix. This is because every operation even bfs runs with O(V2) and same goes for the dfs.
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
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.
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