Информатика
>>
Книги, журналы
>>
Беров В., Лапунов А., Матюхин В., Пономарев А., Особенности национальных задач по информатике
>>
глава 3. Алгоритмы на графах
>>
задача 15
Фильтр
Выбрана 1 задача
Версия для печати
Убрать все задачи
В некоторой стране протянута сеть железных дорог. Требуется наладить сообщение между двумя различными городами A и B, пустив наибольшее возможное число поездов от A до B. Из-за конструктивных особенностей поездов, нарушений расписания и прочих объективных причин необходимо, чтобы никакие два поезда не проезжали через один город, за исключением,
конечно, городов A и B.
Входные данные
В первой строке входного файла записаны целое число M – количество городов в стране (2 ≤ M ≤ 25) и номера городов A и B (города нумеруются числами от 1 до M). Далее перечислены все железные дороги страны, каждая из них задается парой номеров городов, которые она соединяет. Все дороги считаются одноколейными и ориентированными, то есть ведущими из первого города пары во второй, но не наоборот.
Выходные данные
Выведите в первую строку выходного файла целое число K – максимальное количество поездов, которые можно пустить из A в B. Далее выведите K маршрутов поездов, по одному в каждой строке. Каждый маршрут задается номерами городов, через которые проходят поезда в порядке следования от A до B.
Пример входного файла
5 2 4
2 1
2 3
1 3
3 1
1 4
3 4
3 5
Пример выходного файла
2
2 1 4
2 3 4
Решение
Убрать все задачи
В некоторой стране протянута сеть железных дорог. Требуется наладить сообщение между двумя различными городами A и B, пустив наибольшее возможное число поездов от A до B. Из-за конструктивных особенностей поездов, нарушений расписания и прочих объективных причин необходимо, чтобы никакие два поезда не проезжали через один город, за исключением,
конечно, городов A и B.
Входные данные
В первой строке входного файла записаны целое число M – количество городов в стране (2 ≤ M ≤ 25) и номера городов A и B (города нумеруются числами от 1 до M). Далее перечислены все железные дороги страны, каждая из них задается парой номеров городов, которые она соединяет. Все дороги считаются одноколейными и ориентированными, то есть ведущими из первого города пары во второй, но не наоборот.
Выходные данные
Выведите в первую строку выходного файла целое число K – максимальное количество поездов, которые можно пустить из A в B. Далее выведите K маршрутов поездов, по одному в каждой строке. Каждый маршрут задается номерами городов, через которые проходят поезда в порядке следования от A до B.
Пример входного файла
5 2 4
2 1
2 3
1 3
3 1
1 4
3 4
3 5
Пример выходного файла
2
2 1 4
2 3 4
Решение
Задачи
Страница: 1 [Всего задач: 1]
В некоторой стране протянута сеть железных дорог. Требуется наладить
сообщение между двумя различными городами A и B, пустив наибольшее
возможное число поездов от A до B. Из-за конструктивных особенностей
поездов, нарушений расписания и прочих объективных причин необходимо,
чтобы никакие два поезда не проезжали через один город, за исключением,
конечно, городов A и B.
Входные данные
В первой строке входного файла записаны целое число M – количество городов в стране (2 ≤ M ≤ 25) и номера городов A и B (города нумеруются числами от 1 до M). Далее перечислены все железные дороги страны, каждая из них задается парой номеров городов, которые она соединяет. Все дороги считаются одноколейными и ориентированными, то есть ведущими из первого города пары во второй, но не наоборот.
Выходные данные
Выведите в первую строку выходного файла целое число K – максимальное количество поездов, которые можно пустить из A в B. Далее выведите K маршрутов поездов, по одному в каждой строке. Каждый маршрут задается номерами городов, через которые проходят поезда в порядке следования от A до B.
Пример входного файла
5 2 4
2 1
2 3
1 3
3 1
1 4
3 4
3 5
Пример выходного файла
2
2 1 4
2 3 4
Страница: 1 [Всего задач: 1]
Задача 102898[Поможем МПС ] |
|
|
конечно, городов A и B.
Входные данные
В первой строке входного файла записаны целое число M – количество городов в стране (2 ≤ M ≤ 25) и номера городов A и B (города нумеруются числами от 1 до M). Далее перечислены все железные дороги страны, каждая из них задается парой номеров городов, которые она соединяет. Все дороги считаются одноколейными и ориентированными, то есть ведущими из первого города пары во второй, но не наоборот.
Выходные данные
Выведите в первую строку выходного файла целое число K – максимальное количество поездов, которые можно пустить из A в B. Далее выведите K маршрутов поездов, по одному в каждой строке. Каждый маршрут задается номерами городов, через которые проходят поезда в порядке следования от A до B.
Пример входного файла
5 2 4
2 1
2 3
1 3
3 1
1 4
3 4
3 5
Пример выходного файла
2
2 1 4
2 3 4
|
|
|
Решение |
Страница: 1 [Всего задач: 1]
