Какой алгоритм я должен использовать для этого

Question

Мне нужно написать программу, которая будет определять, сколько детей сможет найти кровать для сна, пока не стемнеет.

Каждый ребенок и каждая кровать имеют свой собственный набор координат (x.x, y.y).

Только один ребенок подходит для одной кровати.

Нет двух детей или кроватей в одном и том же наборе координат.

Каждый ребенок ходит по одному шагу в минуту, так что, например, для ребенка потребуется 3 минуты, чтобы пройти от 22,0, от 0,0 до 19,0, 0,0.

Пример:

Child1 находится в 22,0, 0,0

Child2 находится на 0,0, 19,0

Bed1 находится в 18,0, 0,0

Bed2 находится в 50,0, 14,0

Будет темно через 5 минут, сколько детей может найти кровать в течение 5 минут.

Я искал проблему с максимальным потоком, но я не думаю, что это применимо к моей проблеме.

Answer 1

Для решения этой проблемы вам необходимо реализовать алгоритм двустороннего максимального соответствия (специальный случай максимального потока). Поэтому сначала вам нужно создать график из ваших данных. Подключение каждого ребенка к каждой кровати, за исключением случаев, когда расстояние ребенка до кровати больше, чем время, которое остается, пока не стемнеет. Поскольку двунаправленное максимальное согласование также разрешимо с использованием максимального потока, мы делаем сеть потока из этого графика и решаем его с максимальным потоком. Для этого вы должны создать узел source с емкостью infinity и подключить его ко всем детям, а также создать узел sink с емкостью infinity и подключить каждую кровать к нему. Также назначьте размер размером one всем краям между детьми и кроватями. После этого, выполнив алгоритм максимального потока на этом графике, вы найдете ответ.