Дизайн алгоритма для двухстороннего соответствия .. дети и одежда

Question

Предположим, вы учитель детского сада, и вам нужно, чтобы ваши дети были одеты, чтобы поиграть на улице. Каждому ребенку нужна шляпа, варежки и пальто. У каждого ребенка есть предпочтения, на которых одежда, которую они хотят носить.

У нас есть русские дети, шляпы, парные варежки и куртки. Для каждого ребенка у нас есть список приемлемых шляп, рукавиц и пальто. Разработайте алгоритм, чтобы определить, можно ли получить каждого ребенка в шляпе, варежках и пальто.

Таким образом, эта проблема очень четко связана с двудольной совпадающей задачей. Я знаю, что двудольные графы могут быть решены путем присоединения источника и раковины, создания краев веса 1 и решения типичной проблемы максимального потока.

Мне трудно понять, как решить эту проблему, зная эти вещи. Я думаю, что каждая пара (дети, шляпы), (дети, варежки), (дети, пальто) - их собственный отдельный двудольный граф. Это касается того, насколько я дошел до сих пор, любые намеки или толчки в правильном направлении очень ценятся.

Answer 1

Как нет никакой связи между шляпами, рукавицами и пальто, вы можете безопасно управлять тремя отдельными двухсторонними сопоставлениями для (children,hats), (children.mittens), (children,coats). Тогда ваше решение будет минимальным из этих трех. Поэтому, если минимум их равен общему числу детей, тогда вы можете одеть всех детей.