Задача 102897
|
Название задачи: Покрытие путями . |
 |
Условие
Задан ориентированный ациклический граф. Требуется построить наименьшее количество путей, покрывающих все вершины этого графа и не пересекающихся ни по одной из вершин.Входные данные
В первой строке входного файла записано количество вершин графа 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). Теперь для получения решения
необходимо найти максимальное паросочетание в построенном графе.
