If you are using Edmonds-Karp, chnage it to regular Ford-Fulkerson (do DFS instead of BFS), because the running time in this case is better that way, as the maximum flow can be 1000 at most, so the complexity will be O(V*|f|) <= 2000*1.000.000 and this umber fits in 0.5 seconds. However, in case of E-K, the worst case running time is O(V^2*E) <= 1.000.000 * 1.000.000, which is the case of 1000-1000 complete graph and this exceeds the given 0.5 seconds.