Условие: Номер 21

Задача 21. Янка положил на стол N выпуклых K-гранников и N различных типов наклеек по K штук каждая. Ночью кто-то наклеил наклейки на грани, по одной на грань. Помогите Янке расставить многогранники так, чтобы наклейка каждого типа была видна pовно K-1 раз.

  Решение задачи: Номер 21

Решение задачи 21. Можно сформировать граф, состоящий из 2*N вершин, соответствующих К-гранникам и типу наклеек, причем две вершины соединены ребром, если одна соответствует наклейке, а другая - К-граннику, при этом наклейка соответствующего типа находится на соответствующем К-граннике. Добавив в этом графе 2 новые вершины, одна из которых смежна всем вершинам, соответствующим типам наклеек, а другая - всем вершинам, соответствующим К-гранникам, сведем задачу к задаче нахождения максимального потока между этими вершинами.

Назад