World's most popular travel blog for travel bloggers.

# It is necessary to minimize the functional

, ,
Problem Detail:

Consider the town as a grid $N$ x $N$. Thus, there are $(N+1)(N+1)$ of junctions and $2N(N+1)$ two-way roads. Every intersection has a height. It is known that the upper left intersection has a height of $0$, and the lower right the height $1$. For each road we know how many people go in each direction on this road. In this case, if the road leads from the intersection $i$ to the intersection $j$ and the height difference $h = h_j - h_i$, the inconvenience of moving every person on this road is equal to $\max(h, 0)$. For all intersections except two angle are allowed to choose any height. It is necessary to minimize the total inconvenience. In the end, it is necessary to obtain only a total inconvenience, the individual heights are not needed.

I think all heights will lie in the set $\{0, 1\}$. It is clear that you can honestly cycle through all the bitmaps and choose the best. But you need to find more efficient algorithm. One of my ideas was to put all the intersections in the upper left part of the height equals $0$, and the right lower part of the height equal to $1$. Here would be required to find the optimal boundary. I came up with a way of solving by finding maximum flow of minimum cost in $O(N^8)$. Can it be better?

Example:

P. S. Sorry for my bad English.

This problem is exactly the problem of finding the minimum $(s,t)$ cut in a directed graph, where $s$ is the upper-left corner and $t$ is the lower-right corner. All the vertices on the $s$ side of the cut will be assigned height 0; all the vertices on the $t$ side of the cut will be assigned height 1; and the capacity of the cut is equal to the sum of the counts on the edges that cross the cut in the $s\to t$ direction. You want to minimize this sum, so you want to find the minimum $(s,t)$ cut. There are many standard algorithms for doing that, based on finding a maximum flow and then applying the min-cut max-flow theorem.