|
Поздравление с Новым Годом
Time limit = 1 секунд(ы)
Петя хочет поздравить своих друзей с новым годом. У него есть N открыток и K конвертов. Некоторые открытки не помещаются в некоторые конверты. Петя хочет поздравить максимальное количество друей (а их у него очень-очень много). Но он совсем не умеет программировать. Помогите ему — напишите программу, которая определяет, в какие конверты какие открытки класть, чтобы поздравить максимальное количество друзей.
Вход: В первой строчке находятся натуральные числа N, K, C, разделенные пробелами. За ними следует C пар чисел. Открытку номер A можно поместить в конверт номер B только тогда, когда во входе есть пара (A, B).
Выход: Первая строчка выхода должна содержать X — максимальное число поздравлений. Следующие X строчек содержать X пар натуральных чисел, первое число в паре — номер открытки, а второе — номер конверта.
Если есть несколько решений, представьте одно из них.
Ограничения: 0 ≤ N, K ≤ 1000, 0 ≤ C ≤ 12000.
Подскажите, пожалуйста, алгоритм решения! Я написал программу, в которой реализуется метод простого рекурсивного поиска с некоторыми конкретными оптимизациями. Оптимизации заключаются только в том, что рекурсия обрывается при выполнении некоторых дополнительных условий. Это ускоряет алгоритм тупого перебора "в лоб", но получается все равно медленно. То есть, фактически, я просто перебираю все возможные размещения открыток по конвертам и ищу максимум. Приводить его нет смысла. Нужен хороший алгоритм.
Некоторые (очевидные) мысли по поводу задачи. 1) Если в какой-то конверт вообще можно поместить только одну открытку, то её следует туда поместить "намертво", вне зависимости от остальных данных. Тогда эта открытка в последующем переборе уже не участвует. 2) Если на данном наборе в итоге получилось, что конверт остался пустой, но в него возможно поместить некоторые открытки, то можно поместить в него какую-нибудь их этих открыток, предварительно вытащив её из своего конверта. "Ущерба" набору не будет.
Но более или менее эффективный алгоритм мне составить не удалось. Буду благодарен любой помощи и наводкам! Мне кажется, задача довольно общая (есть два множества, между некоторыми элементами первого и второго множества возможна связь. Какое максимальное кол-во связей возможно одновременно при сохранении взаимной однозначности?), так что алгоритм по-любому быть должен. Спасибо!
|
, например,