13
Шешімі: Пути через город К
ЕГЭ · Информатика · Тапсырма 13 · Графы и пути
КүрделіФИПИ0F204AҚысқа жауап≈ 3 минутТалдау 2 қадамЖауап сверен с ключом
Условие
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город К?
Дальше ответЕгер әлі шешіп жатсаңыз – кеңестерден бастаңыз: олар жауапқа жетелейді, бірақ оны ашпайды.
К подсказкамШешім по шагам
2 қадам1
Каждый путь из А в М, проходящий через К, однозначно состоит из двух частей: пути из А в К и пути из К в М.
$$N_{A\to M\ через\ K}=N_{A\to K}\cdot N_{K\to M}$$Подсчитываем число направленных путей по схеме динамически: для каждой вершины складываем количества путей, ведущих в неё из предыдущих вершин. После этого перемножаем результаты для участков А–К и К–М.
$$N_{A\to K}\cdot N_{K\to M}=42$$Жауап
42
42
так ответ выглядит в бланкеГде здесь ошибаются
Учитывают пути, которые не проходят через город К.
Считают дороги вместо различных направленных путей.
Не учитывают направление стрелок.