Soluções Mapa

0 Flares Facebook 0 0 Flares ×

Primeiramente, note que o grafo é uma árvore. Se quisermos todos os caminhos que passam por determinado tipo de aresta, eliminamos todas essas arestas e nos restará uma floresta (várias componentes conexas e cada uma é uma árvore). Então, fica fácil ver que os caminhos que passam por um tipo de aresta são os caminhos entre vértices de componentes conexas distintas.

Seja k o número de componentes conexas e c_1, c_2, ..., c_k o número de vértices em cada uma delas. Queremos, então, a soma dos produtos dois a dois dos c_i's. Para fazer isso de maneira linear (quadrática estouraria o tempo!), usamos o fato de que:

(c_1 + c_2 + ... + c_k)^2 = (c_1^2 + c_2^2 + ... + c_k^2) + 2(c_1 c_2 + c_1 c_3 + ... + c_2 c_3 + ... + c_{k-1} c_k)

e podemos calcular os dois primeiros termos de maneira linear.

Para calcular os c_i's. podemos fazer um algoritmo de Flood Fill ou Union Find (vide as aulas do Curso Noic).

O código, então, fica:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: