ROBOTDAG - Editorial

No two robots should pass through an edge at a fixed time. Let us consider an edge (u, v), we want that for each time t from 0 to n - 1, there shouldn’t be two robots crossing this edge. We construct a graph as follows. The nodes of the graph will be (u, t), where u will correspond to the vertex and t the time. For each edge (u, v), we add an edge (u, t) to (v, t + 1) for each t from 0 to n-1. Our original problem now reduces to find edge-disjoint paths in this new graph. Note that we will be adding edges 0, u for only time t = 0. Similarly, we add an edge between (n - 1, t) to (n - 1, t + 1) for each t denoting that if the robot lands at the target node n-1, it can stay there forever.

In this graph, the max flow with source (0, 0), and sink (n - 1, t) will correspond to the maximum number of robots that we can send. We want to find the least t such that the maximum number of robots becomes \geq K. This can be done using binary search.

//