Solução Imperialismo

0 Flares Facebook 0 0 Flares ×

Solução de Pedro Michael, comentários de Rogério Júnior

Para ver o problema original, clique aqui.

 

Observe o pior caso possível: uma a uma, todas as cidades do maior caminho do grafo são conquistadas por uma das cidades das pontas. Neste caso, se o maior caminho tivesse tamanho d, ele demoraria exatamente \big\lceil\frac{d}{2}\big\rceil anos para ser totalmente conquistado. Desse modo, basta descobrirmos o tamanho d do maior caminho numa árvore (seu diâmetro) e imprimirmos o valor de \big\lceil\frac{d}{2}\big\rceil.

Para descobrir o diâmetro de um árvore, escolhemos um vértice qualquer v_ori e encontramos seu vizinho mias distante v_1. Depois, encontramos o vértice v_2, vizinho mais distante de v_1, e o caminho de v_1 a v_2 é um diâmetro, e tem comprimento d máximo.

Segue o código para melhor entendimento:

 

 

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