Minimum time to start the race

Question

There are N bikers present in a city (shaped as a grid) having M bikes. All the bikers want to participate in the competition, but only K bikers can be accommodated in the race.

In order to minimize the time to start the race, bikers move for getting the bikes spread in the city in such a way that first K bikes are acquired in the minimum time.

Every biker moves with a unit speed and one bike can be acquired by only one biker. A biker can proceed in any direction. Distance between bike and bikers is euclidean distance.

What would be the square of required time to start the race as soon as possible.?

EXAMPLE : Let say we have N=3 that means 3 bikers and let say M=3 meaning 3 bikes are their and suppose K=2 means we need only 2 bikers for race

Coordinates of bikers are : (0,1),(0,2),(0,3)

Coordinates of bikes are : (100,1),(200,2),(300,3)

Then here answer will be 400 as there’s need for two bikers for the race. The first biker (0,1) will be able to reach the first bike (100,1) in 100 time units. The second biker (0,2) will be able to reach the second bike (200,2) in 200 time units. This is the most optimal solution and will take 200 time units. So output will be 200^2 = 40000.

Help to solve this problem?

Constraints are : N,M <= 250

Answer 1

Write down the M*N edges between bikes and bikers. Start throwing them away one by one, longest to shortest, and when the last edge that connects a particular bike (or biker) is thrown away, eliminate that bike (or biker) too. Stop when you cannot pair K bikes to K bikers any more. (This can be tested by e.g. running the Hopcroft–Karp algorithm at each step).

The last edge thrown away (its length squared) is your answer.