796. Стабильное бракосочетание

Задача стабильного бракосочетания состоит в установлении отношений между членами двух множеств в соответствии с их предпочтениями. Входные данные состоят из:

· множества M из n мужчин;

· множества F из n женщин;

· для каждого мужчины и каждой женщины имеется список членов противоположного пола, заданный в порядке предпочтения (от наиболее предпочтительного до наименее).

Бракосочетанием будем называть однозначное отображение между мужчинами и женщинами. Бракосочетание будем называть стабильным, если не существует такой пары (m, f) что f Î F предпочитает m Î M своему текущему партнеру, а m предпочитает f своему текущему партнеру. Стабильное бракосочетание A называется оптимальным по отношению к мужчинам, если не существует такого стабильного бракосочетания B, в котором какому-нибудь мужчине соответствует женщина, которую он больше предпочитает, нежели та, которая присвоена ему в A.

По заданным спискам предпочтений для каждого мужчины и каждой женщины следует найти стабильное бракосочетание, оптимальное по отношению к мужчинам.

Вход. Первая строка содержит количество тестов. Первая строка каждого теста содержит целое число n (0 < n < 27). В следующей строке заданы имена n мужчин и n женщин. Мужские имена начинаются прописными буквами, а женские заглавными. Далее идут n строк, которые описывают списки предпочтений для мужчин. Следующие n строк описывают списки предпочтений для женщин.

Выход. Для каждого теста следует вывести пары стабильного бракосочетания, оптимального по отношению к мужчинам. Пары следует выводить в лексикографическом порядке мужских имен как показано в примере. Между тестами следует выводить пустую строку.

Пример входа

2

3

a b c A B C

a:BAC

b:BAC

c:ACB

A:acb

B:bac

C:cab

3

a b c A B C

a:ABC

b:ABC

c:BCA

A:bac

B:acb

C:abc

Пример выхода

a A

b B

c C

a B

b A

c C

РЕШЕНИЕ

жадный алгоритм

Анализ алгоритма

while существует холостой мужчина m do

{

мужчина m берет в пару женщину f, которую предпочитает больше всего и которую

он еще не брал в пару;

if женщина f не в паре then создать пару (m, f);

else if f предпочитает m текущему мужчине m’ в паре then

{

сделать m’ холостым;

создать пару (m, f);

}

else m остается холостым;

}