Nome: Sistema Cipoviário
Link: http://br.spoj.pl/problems/CIPO/
Dificuldade: 8/10
Linguagem: C++
Tempo atingido: 8.20
Memória usada: 33M
Colocação alcançada: 100+
Tentativas: 5
Comentário:
Ta aí, mais um exercício de busca de caminho em grafos.
Dessa vez é pra encontrar a Árvore geradora mínima.
Eu estudei dois métodos, entre eles o algoritmo de Prim e o de Kruskal.
O de Prim acabou dando zebra, porque, de acordo com o que disseram nos comentário e também no fórum, o grafo é desconexo, diferente do que diz o enunciado.
Em um grafo desconexo o algoritmo de Prim não encontrará todas as arestas.
Portanto foi necessário utilizar o algoritmo de Kruskal.
O resultado, portanto, deve ser a soma da árvore geradora mínima de todas as árvores.
Dicas:
- Estudem o algoritmo de Kruskal.
- Estudem Union-Find, para melhor aplicar o algoritmo de Kruskal.
- Notem que há apenas três valores, portanto a ordenação pode ser feita de uma maneira bem otimizada.
Nenhum comentário:
Postar um comentário