Analysis 080912

Bring Your Own Horse

Faça a Minimum Spanning Tree do grafo dado; com ela, é possível achar a menor maior aresta entre os vértices k,t em O(n), que é o suficiente para responder todas as queries. Isso funciona porque a Minimum Spanning Tree contém os caminhos com as menores arestas que conectam o grafo (algo que é bastante óbvio se você pensar sobre o algoritmo de Kruskal).
Para o maior aresta em O(n), como só existe um caminho entre dois vértices u,v numa árvore, achar o peso da menor aresta é fazer uma DFS a partir de u até você achar v, guardando a maior das arestas que você passar.
Minha solução: http://pastebin.com/228yudAH

First Knight

Postal Charges

Randomly-Priced Tickets

The Game

The Merchant Guild

Toll Road

Top Secret

Transcribed Books

Wizards

Nota:

Como essa prova é SWERC, tem uma documentação bem bacana disponibilizada, com as ideias das soluções e implementações aqui

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License