Задача 8.
Имеется N прямоугольных конвертов и N прямоугольных открыток различных размеров. Можно ли разложить все открытки по конвертам, чтобы в каждом конверте было по одной открытке.
Замечание. Открытки нельзя складывать, сгибать и т.п., но можно помещать в конверт под углом. Например, открытка с размерами сторон 5:1 помещается в конверты с размерами 5:1, 6:3, 4.3:4.3, но не входит в конверты с размерами 4:1, 10:0.5, 4.2:4.2.
|
Решение задачи 8.
Можно сформировать граф, состоящий из 2*N вершин, соответствующих открыткам и конвертам, причем две вершины соединены ребром, если одна соответствует открытке, а другая - конверту, при этом соответствующая открытка входит в соответствующий конверт. Добавив в этом графе 2 новые вершины, одна из которых смежна всем вершинам, соответствующим открыткам, а другая - всем вершинам, соответствующим конвертам, сведем задачу к задаче нахождения максимального потока между этими вершинами.
|
