開始比賽的最短時間

Question

有一輛M騎車的城市（形狀爲網格）有N個騎車人。所有的騎手都想參加比賽，但只有K騎手可以參加比賽。

爲了儘量減少比賽開始時間，騎自行車的人可以在最短的時間內獲得首輛K型自行車。

每個騎車人以單位速度移動，一輛自行車只能由一個騎車人獲得。騎自行車的人可以朝任何方向前進。自行車和騎自行車的距離是歐式距離。

儘快開始比賽需要的時間平方是多少？

示例：假設我們有N = 3，這意味着3個騎自行車的人，讓說，M = 3，這意味着3輛自行車是他們的，並假設K = 2意味着我們只需要2騎自行車的種族騎自行車的

座標是：（0,1），（0,2），自行車（0,3）

座標是：（100,1），（200,2），（300,3）

然後這裏的回答將是400，因爲比賽需要兩名騎手。第一個騎自行車的人（0,1）將能夠以100個時間單位到達第一輛自行車（100,1）。第二個騎車人（0,2）將能夠以200個時間單位到達第二輛自行車（200,2）。這是最優化的解決方案，需要200個時間單位。所以輸出將會是200^2 = 40000.

有幫助解決這個問題嗎？

約束是：N，M < = 250

Answer 1

記下所述M * N自行車和騎自行車之間的邊緣。開始把他們逐個扔掉，最長到最短，並且當連接特定自行車（或騎車人）的最後邊緣被扔掉時，也要消除該自行車（或騎車人）。當你無法將K自行車與K騎自行車的人配對時停下來。 （這可以通過例如在每個步驟運行Hopcroft–Karp algorithm來測試）。

扔掉的最後一個邊（它的長度平方）就是你的答案。