|
Дистанционный практикум по программированию
|
| Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь. |
196. Покрытие путями
|
| Статистика | Послать на проверку | Задачу добавил Administrator |
|
Условие
Задан ориентированный ациклический граф. Требуется построить наименьшее количество путей, покрывающих все вершины этого графа и не пересекающихся ни по одной из вершин. Входные данныеВ первой строке записано количество вершин графа N (1 <= N <= 25). Далее перечислены ребра графа, заданные номерами начальной и конечной вершин. Выходные данные Выведите число K - наименьшее количество путей, которыми можно покрыть все вершины графа. Пример входного файла 4 1 2 1 3 2 3 2 4Пример выходного файла 2 |
| Статистика | Послать на проверку | Автор/источник: |
| Задачи по темам / | Графы / |
| 204. Пиво в розлив | 196. | 195. Поможем МПС | 246. Путь в лабиринте | 9. Сеть |
| Задачи с соревнований / | Тренировки ВоГТУ / | Тренировка 21.09.2006 / |
| 194. F - умножение многочленов | 196. | 195. Поможем МПС |
| время генерации 0.156 сек. | |
| © Copyright ВоГТУ, АВТ, Носов Д.А. |