zadanie Wybuchowa Owca

ďťż

Damian Rusak - 28 mar 2010, o 11:00
" />Zadanie Wybuchowa Owca było dosyć ambitne. Może ktoś chciałby podzielić się pomysłem na jego rozwiązanie?;)

Przemysław Derengowski - 28 mar 2010, o 14:46
" />Ciekawiło mnie czemu dostało tylko 2 gwiazdki trudności. Co do rozwiązania, to można skorzystać z tej strony: http://www.astagor.net/putinf/data/algo ... pojne.html. Tutaj od razu narzuca się wyznaczenie mostów. Mój algorytm wygląda tak:
- spr czy wilk i owca nie są w różnych składowych
- wyznacz mosty O(n+m)
- policz odległości od owcy i wilka do wszystkich wierzchołków algorytmem Dijkstry O(m lg n)
- dfs od wilka, w momencie gdy jesteśmy po jednej stronie mostu (a nie byliśmy po drugiej), patrzymy czy owca może dojść na drugą stronę przed wilkiem jeśli tak, to porównujemy czas dojścia owcy z najmniejszym dotychczasowym O(n+m)
- wypisujemy minimum, lub NIE jeśli minimum = infinity;

Czas O(m lg n), pamięć O(n+m).

Darmowy hosting zapewnia PRV.PL