112, Маша пришла в лес за грибами. У неё есть план леса в виде графа (рис. 66). Вершины гра- фа - это полянки в лесу, рёбра — это тропинки. Чтобы не заблудиться, идти по тропинке можно только в указанном направлении. На некоторых полянках растут грибы, их количество указано внутри вершин. Какое наибольшее количество грибов она может со- брать?

Для решения задачи необходимо найти путь от входа к выходу, который позволит собрать наибольшее количество грибов. Нужно учитывать, что двигаться можно только в указанном направлении. Рассмотрим граф (рисунок 66) и вычислим максимальное количество грибов, которое можно собрать, двигаясь от входа к каждой вершине: 1. Начальная вершина (Вход): 0 грибов. 2. Вершина 8: 0 + 8 = 8 грибов. 3. Вершина 2: 8 + 2 = 10 грибов. 4. Вершина 6: 10 + 6 = 16 грибов. 5. Вершина 1: 10 + 1 = 11 грибов. 6. Вершина 5 (левая): 8 + 5 = 13 грибов. 7. Вершина 5 (правая): 1 + 5 = 6 грибов. 8. Вершина 3: 6 + 3 = 9 грибов. 9. Вершина 4: 5 + 4 = 9 грибов. 10. Вершина 2 (правая): 3 + 2 = 5 грибов. 11. Вершина 1 (выход): * Из вершины 6: 16 + 1 = 17 грибов. * Из вершины 5: 13 + 1 = 14 грибов. * Из вершины 3: 9 + 1 = 10 грибов. * Из вершины 4: 9 + 1 = 10 грибов. * Из вершины 2: 5 + 1 = 6 грибов. Максимальное количество грибов, которое можно собрать, составляет 17. Ответ: 17