PROBLEM LINK:
Editorialist: Jingbo Shang
DIFFICULTY:
Cakewalk
PREREQUISITES:
Manhattan Distance
PROBLEM:
Given a K*K grid, a source intersection, and a set of target intersections (there are no targets on the same row and column of the source), set the directions of all edges such that all intersections are strongly connected and the total distance from source to targets are minimum.
EXPLANATION:
If the edges remain bi-direction, the minimum distance is the Manhattan distance. If we can construct a plan such that the total distance is equal, it is definitely the best solution.
Fortunately, it is possible. Here we introduce a possible plan, as shown in the following figure. First, we should observe that there are no targets on the same row and column of the source. From this property, we can divide the grid into 4 parts (less if the source is on the boundary, but similar). Using the borders of each part, we can make 4 loops. With these 4 loops, if every intersection is reachable from the source and it can also reach one of the loop, then we can travel from the source, visit that intersection, and then back to the source. And thus, the girds are strongly connected. Therefore, we direct the rows in each part, such that every intersection can be reached from source and can reach the loop. Furthermore, the distance is now equal to the Manhattan distance, which means this is a optimal solution.