I had to play with optimizations to get this one. I have a pre-written maxflow, but it is in C++ and uses some STL (basically just a bunch of vectors). Of course, here at UVa the judge has an old g++, and compiles without the for-STL-necessary -O2, so this was quite a setback. This solution didn't pass even the 10 seconds time limit.Cho wrote:I've tried the same approach after reading your post, but TLE.misof wrote:I'm down to 2.870
Could you tell me whether you use the same maxflow routine as your 10983 (Buy one, get the rest free) to solve this problem?
The first step was basically to rewrite it to plain C -- a global int G[][] instead of a vector< vector<int> > &G passed as a parameter, and such.
Other optimizations include:
- once the current flow exceeds your so-far-best cut, terminate it
- using a heuristic to get the first bound on the mincut (cutting off any one vertex)
- I fix a vertex v and search all pairs [v,w], I use an heuristic to choose v so that the above pruning is expected to be a bit more effective.\
One other optimization I didn't implement: run BFS first, and process the vertices w in decreasing distance order.
