Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 2 ] 
zadanie Wybuchowa Owca 
Autor Wiadomość
Gwiazda 3
Avatar użytkownika

Dołączył(a): 27 maja 2009, o 18:20
Posty: 126
Post zadanie Wybuchowa Owca
Zadanie Wybuchowa Owca było dosyć ambitne. Może ktoś chciałby podzielić się pomysłem na jego rozwiązanie?;)


28 mar 2010, o 12:00
Zobacz profil
Gwiazda 3Gwiazda 3

Dołączył(a): 17 lis 2009, o 02:37
Posty: 141
Post Re: zadanie Wybuchowa Owca
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).


28 mar 2010, o 15:46
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 2 ] 


Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 2 gości


Nie możesz rozpoczynać nowych wątków
Nie możesz odpowiadać w wątkach
Nie możesz edytować swoich postów
Nie możesz usuwać swoich postów
Nie możesz dodawać załączników

Szukaj:
Skocz do:  
cron


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group. Forum style based on STSoftware Hestia.
Przyjazne użytkownikom polskie wsparcie phpBB3 - phpBB3.PL