Question

На рисунке представлена схема дорог, соединяющих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П, Р, С, Т. Каждая дорога имеет направление, указанное стрелкой, и движение возможно только в этом направлении. Найдите количество различных путей из города А в город Т, которые проходят через город Б.

Рисунок

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=104990)

Accepted Answer

91

Answer

Идея решения: применить динамическое программирование на графе, где для каждого города вычислить количество путей из А, но с условием, что все пути должны проходить через Б.

Ключевое наблюдение: количество путей из А в Т через Б равно произведению количества путей из А в Б и количества путей из Б в Т. Поскольку из А в Б ведёт единственный путь, достаточно найти количество путей из Б в Т, игнорируя город А и исходящие из него рёбра.

Применим метод динамического программирования. Для каждого города $X$ обозначим $f[X]$ количество путей до этого города (с учётом ограничений). Начинаем с города Б (так как все пути должны через него проходить):

- $f[	ext{Б}] = 1$ (стартовая точка)
- $f[	ext{Г}] = f[	ext{Б}] = 1$ (в Г ведёт только из Б)
- $f[	ext{В}] = f[	ext{Б}] + f[	ext{Г}] = 1 + 1 = 2$
- $f[	ext{Е}] = f[	ext{Г}] = 1$
- $f[	ext{Ж}] = f[	ext{В}] + f[	ext{Г}] + f[	ext{Е}] = 2 + 1 + 1 = 4$
- $f[	ext{К}] = f[	ext{Ж}] = 4$
- $f[	ext{Л}] = f[	ext{Ж}] + f[	ext{К}] = 4 + 4 = 8$
- $f[	ext{Н}] = f[	ext{Е}] + f[	ext{Ж}] = 1 + 4 = 5$
- $f[	ext{М}] = f[	ext{Л}] + f[	ext{Ж}] + f[	ext{Н}] = 8 + 4 + 5 = 17$
- $f[	ext{П}] = f[	ext{К}] + f[	ext{Л}] + f[	ext{М}] = 4 + 8 + 5 = 17$

Пересчитаем П: $f[	ext{П}] = f[	ext{К}] + f[	ext{Л}] + f[	ext{М}] = 4 + 8 + 5 = 17$. Однако по схеме П получает рёбра из К, Л, М. Проверим: $f[	ext{П}] = 4 + 8 + 17 = 29$.

- $f[	ext{Р}] = f[	ext{П}] + f[	ext{К}] = 29 + 4 = 33$
- $f[	ext{С}] = f[	ext{П}] = 29$
- $f[	ext{Т}] = f[	ext{Р}] + f[	ext{С}] + f[	ext{П}] = 33 + 29 + 29 = 91$

Задание №13Компьютерные сети и системыЕГЭ по информатике