Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 5 ] 
[Rozwiązania] Trasy 
Autor Wiadomość
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 24 lis 2009, o 15:59
Posty: 47
Post [Rozwiązania] Trasy
Ktoś się pochwali zgrabnym kodem tegoż zadania? Bo moje rozwiązanie było strasznie obszerne. Najpierw tworzyłem DAG (directed acyclic graph) z wyciągów, i obliczałem standardowo liczbę ścierzek z każdego punktu gdzie zaczyna się wyciąg do każdego punktu gdzie kończy się wyciąg, czyli tabelka K*K = 300*300, następnie z każdego punktu gdzie kończy się wyciąg na mapie ten sam algorytm wyliczania liczby ścierzek do wszystkich punktów na mapce czyli K*N*M potem to ładnie wymnażałem dla każdej pary punktów gdzie zaczyna się i kończy wyciąg i sumowałem wszystko do wyniku.
Udało się 10/10.
Czas ostatnich testach 29 82 102 ms.
Ktoś miał jakieś inne rozwiązania?


15 kwi 2011, o 22:23
Zobacz profil
Gwiazda 1Gwiazda 1Gwiazda 1

Dołączył(a): 30 paź 2010, o 12:53
Posty: 1
Post Re: [Rozwiązania] Trasy
Dokładnie tak samo chciałem robić, tylko nie wiem jak się szuka ilości ścieżek. Mógłbyś powiedzieć jakiego "standardowego" algorytmu użyłeś?

btw, ścieżek, aż oczy bolą :P


15 kwi 2011, o 22:28
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 11 paź 2010, o 17:26
Posty: 100
Post Re: [Rozwiązania] Trasy
Jeśli o mnie chodzi to najpierw generowałem wszystkie możliwe wyciągi (tzn pkt. do których mogłem dostać się różnymi wyciągami, tu możliwe, że zrobiłem błąd) po czym dla każdej możliwości rekurencyjnie spr. ilość dróg powrotnych do pkt z którego wyruszyłem. Niestety prawdopodobnie generowanie źle napisałem przez co mam tylko 1 pkt ;)

@up nie musisz znać ilości ścieżek, musisz znać dla każdej pkt startu i punkt końcowy :) Przynajmniej w moim rozumowaniu, możliwe, że @Michał miał inny koncept (lub Ty).


15 kwi 2011, o 22:31
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 17 lis 2009, o 13:38
Posty: 43
Post Re: [Rozwiązania] Trasy
Karol Lisiecki napisał(a):
Dokładnie tak samo chciałem robić, tylko nie wiem jak się szuka ilości ścieżek. Mógłbyś powiedzieć jakiego "standardowego" algorytmu użyłeś?

btw, ścieżek, aż oczy bolą :P


No jak mamy dag to możemy wierzchołki posortować topologicznie, ustawiamy ilość ścieżek dla pierwszego wierzchołka na 1 i idziemy przez wszystkie wierzchołki (np BFS) aktualizując liczbę ścieżek : d[v] += d[u]

To tak w skrócie :)


15 kwi 2011, o 22:33
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 2 sie 2010, o 14:04
Posty: 11
Post Re: [Rozwiązania] Trasy
Norbert Gregorek napisał(a):
Karol Lisiecki napisał(a):
Dokładnie tak samo chciałem robić, tylko nie wiem jak się szuka ilości ścieżek. Mógłbyś powiedzieć jakiego "standardowego" algorytmu użyłeś?

btw, ścieżek, aż oczy bolą :P


No jak mamy dag to możemy wierzchołki posortować topologicznie, ustawiamy ilość ścieżek dla pierwszego wierzchołka na 1 i idziemy przez wszystkie wierzchołki (np BFS) aktualizując liczbę ścieżek : d[v] += d[u]

To tak w skrócie :)


Można też zapuścić DFSa na transponowanym grafie, który dynamicznie aktualizuje ilość ścieżek.


15 kwi 2011, o 23:48
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 5 ] 


Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 0 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