ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 102897
Тема:    [ Паросочетания ]
Сложность: 3+
Классы:
Название задачи: Покрытие путями .
В корзину
Прислать комментарий

Условие

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

Входные данные

В первой строке входного файла записано количество вершин графа N (1 ≤ N ≤ 25). Далее перечислены ребра графа, заданные номерами начальной и конечной вершин.

Выходные данные

Выведите в первую строку выходного файла число K – наименьшее количество путей, которыми можно покрыть все вершины графа. Далее выведите сами эти пути (по одному в каждой строке), задавая их номерами вершин в порядке посещения.

Пример входного файла

4
1 2
1 3
2 3
2 4

Пример выходного файла

2
1 2 4
3

Решение

Скачать архив тестов и решений

Предположим, что решение задачи состоит из M путей, а R – суммарное количество ребер в этих путях. Каждый путь из L вершин содержит L-1 ребро. Просуммировав по всем путям, получаем, что N - M = R. Следовательно, задача о покрытии минимальным количеством путей эквивалентна задаче о покрытии такими путями, суммарное количество ребер в которых максимально. А это, в свою очередь, равносильно нахождению наибольшего множества ребер с тем свойством, что в каждую вершину входит и из каждой вершины выходит не более одного ребра данного множества (здесь мы пользуемся ацикличностью графа).


Будем решать последнюю из сформулированных задач. Для этого построим двудольный граф, вершины обеих долей которого соответствуют вершинам исходного графа. При этом вершина a первой доли будет соединена ребром с вершиной b второй доли в том и только том случае, когда в исходном графе существует ориентированное ребро (a, b). Теперь для получения решения необходимо найти максимальное паросочетание в построенном графе.

Источники и прецеденты использования

книга
предмет информатика
Автор Беров В., Лапунов А., Матюхин В., Пономарев А.
Название Особенности национальных задач по информатике
Издательство Триада-С
Год издания 2000
глава
Номер 3
Название Алгоритмы на графах
Задача
Номер 14

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .