Push relabel algorithm got TL on test 30.
Dinic with scaling got AC in 0.249 s.
Interestingly, push-relabel algorithm (with some optimizations) that I used is usually a little bit faster than my Dinic with scaling.

There are 2 different ways to solve this problem. The first one is to optimize one of the standard Maxflow algorithms to pass TL. The second one is to use the planarity of graph, design an algorithm that is asymptotically faster than the standard ones, and get AC with it.

Exuse me!.Brilliant the problem, thank the authors.
We build dual graph and use Dejkstra in it- O(nlog(n)).
But computing dual graph is separated difficult problem
from computational geometry connected with walking on grid
with extacting faces.

Now I am implementing this approach.
In test 14 I have situation when starting from some
edge and making maximal possible turn to left we don't
return to starting edge. Is it possible in
comlex geometry or bug in program.

Edited by author 18.07.2009 11:05

Does Dinic need some optimisation? It is O(n^2 * m) algorithm. This complexity is too large for 10^4 vertexes and 3*10^4 edges.

Flat graph with N vertices can have maximum 2*N-3 edges, so the problem input is not so large