PUERTA | PUERTA CS 2021 | Juego 2 | Pregunta 65

En un gráfico acíclico dirigido con un vértice fuente s, la puntuación de calidad de un camino dirigido se define como el producto de los pesos de los bordes en el camino. Además, para un vértice v distinto de s, el puntaje de calidad de v se define como el máximo entre los puntajes de calidad de todos los caminos de s a v. Se supone que el puntaje de calidad de s es 1.

La suma de los puntajes de calidad de todos los vértices en el gráfico que se muestra arriba es _______.
(A) 929
(B) 81
(C) 729
(D) 1023

Respuesta: (A)
Explicación: Sea Q(V) la puntuación de calidad del vértice 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) 

Suma de la puntuación de calidad de todos los vértices,

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

Cuestionario de esta pregunta