https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=419168&view=findpost&p=3834374 Fri, 17 Jul 2020 14:47:07 +0000 https://forum.sources.ru/index.php?showtopic=419168&view=findpost&p=3834374 Часть 1, № 15
Задание взято с сайта
http://kotolis.ru/realegeinf_2020



Условие. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какая наибольшая длина пути из А в М?
Решение.
На рисунке изображён ненагруженный ориентированный граф, все дуги которого одинаковы. Будем считать, что каждая дуга имеет длину, равную 1. Длина пути между двумя вершинами равна количеству входящих в него дуг.
Заметим, что все пути из А в М проходят через вершину И. Такие вершины будем называть «контрольные пункты». Теперь задачу поиска самого длинного пути из А в М можно разбить на две подзадачи:
1. найти самый длинный путь из А в И;
2. найти самый длинный путь из И в М.
Эти подзадачи решаются независимо друг от друга, затем решение этих подзадач соединяется в решение исходной задачи.
Вначале решим подзадачу 2. Самый длинный путь от И до М состоит из двух дуг, его длина равна 2.

Будем решать подзадачу 1 двигаясь от конца (вершины И) к началу (вершине А).
Рассмотрим все дуги, которые входят в вершину И: Е -> И, Ж -> И, З -> И. На этот раз у нас получилось три эквивалентные задачи. Чтобы попасть из А в И, можно:
1) найти самый длинный путь из А в Е;
2) найти самый длинный путь из А в Ж;
3) найти самый длинный путь из А в З.
Решим каждую из этих трёх задач и выберем максимальное решение (самый длинный путь).
В первой и третьей задаче самый длинный путь имеет длину 3.
Решим вторую задачу о максимальном пути из А в Ж.
Для вершины Ж рассмотрим все входящие в неё дуги: Е -> Ж, З -> Ж, Д -> Ж, Г -> Ж, В -> Ж. Получили 5 эквивалентных задач. Решим их все и выберем максимальный путь.
Самый длинный путь из А в З и из А в Е имеет длину 2; путь из А в Д имеет длину 1; из А в Г – длину 2; А в В – длину 3. Последний путь даст нам самый длинный путь из А в Ж длины 4.

Теперь собираем самый длинный путь из решений всех подзадач:
А -> Ж (4) + Ж -> И (1) + И -> М (2)
4 + 1 + 2 = 7
Ответ: 7 .

Текст здесь
https://yadi.sk/i/PnzBinOAx5_HVA]]> swf ПОМОЩЬ ШКОЛЬНИКАМ