|
Remote Training on Programming
|
| Hello, Guest! Login or register. |
196. Покрытие путями
|
| View Problem Statistics | Submit | Problem added Administrator |
|
Условие
Задан ориентированный ациклический граф. Требуется построить наименьшее количество путей, покрывающих все вершины этого графа и не пересекающихся ни по одной из вершин. Входные данныеВ первой строке записано количество вершин графа N (1 <= N <= 25). Далее перечислены ребра графа, заданные номерами начальной и конечной вершин. Выходные данные Выведите число K - наименьшее количество путей, которыми можно покрыть все вершины графа. Пример входного файла 4 1 2 1 3 2 3 2 4Пример выходного файла 2 |
| View Problem Statistics | Submit | Author/source: |
| Sorted Problems / | Graphs / |
| 204. Пиво в розлив | 196. | 195. Поможем МПС |
| Problems from Contests / | Trainings of Vologda STU / | Training 21.09.2006 / |
| 194. F - умножение многочленов | 196. | 195. Поможем МПС |
| We can all benefit by doing occasional "toy" programs, when artificial restrictions are set up, so that we are forced to push our abilities to the limit. The art of tackling miniproblems with all our energy will sharpen our talents for the real problems. Donald E. Knuth. |
| time generating 2.403 sec. |
| © Copyright VSTU, AVT, Nosov D.A. |