1552 - Resgate em Queda Livre
Um problema bem direto de montagem de árvore geradora de custo mínimo.
Descrição
Solução
Para conseguirmos o menor comprimento de teia possível para unir todas as pessoas que estão caindo, podemos imaginar primeiramente que todas as pessoas formam um grafo completo onde cada ligação entre uma pessoa i e j indica a distância cartesiana entre essas duas pessoas. É possível formar esse grafo em O(n²) porque temos no máximo 500 pessoas envolvidas.
Com isso, tudo o que precisamos agora é montar a árvore geradora de custo mínimo, a fim de descobrirmos qual a menor quantidade de teia que o Homem-Aranha precisa para ligar todas as pessoas.
Kruskal
Em breve...
Prim
Em breve...
Last updated