ВОРОТА | ВОРОТА КС 2021 | Набор 2 | Вопрос 65

В направленном ациклическом графе с исходной вершиной s показатель качества направленного пути определяется как произведение весов ребер на пути. Кроме того, для вершины v, отличной от s, показатель качества v определяется как максимальный среди показателей качества всех путей из s в v. Предполагается, что показатель качества s равен 1.

Сумма показателей качества всех вершин на графе, показанном выше, равна _______ .
(А) 929
(Б) 81
(С) 729
(Д) 1023

Ответ: (А)
Объяснение: пусть Q(V) обозначает показатель качества вершины V.

Q(S) = 1 (Given)
Q(C) = 1 (S → C)
Q(F) = 1 * 9 (S  → C  → F)
Q(A) = 9 (S  → A)
Q(D) = 9*1 (S  → A  → D)
Q(G) = 9 * 1 * 9 (S  → A  → D  → G)
Q(B) = 9 * 1 (S  → A  → B)
Q(E) = 9 * 1 * 9 (S  → A  → D  → E)
Q(T) = 9*1*9*9 (S  → A  → D  → E → T) 

Сумма показателей качества всех вершин,

= 1 + 1 + 9 + 9 + 9 + 81 + 9 + 81 + 729 
= 929 

Тест на этот вопрос