Wrocławski Portal Informatyczny
http://informatyka.wroc.pl/forum/

[Rozwiązania] Trasy
http://informatyka.wroc.pl/forum/viewtopic.php?f=83&t=1162
Strona 1 z 1

Autor:  Michał Kownacki [ 15 kwi 2011, o 22:23 ]
Tytuł:  [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?

Autor:  Karol Lisiecki [ 15 kwi 2011, o 22:28 ]
Tytuł:  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

Autor:  Damian Dyńdo [ 15 kwi 2011, o 22:31 ]
Tytuł:  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).

Autor:  Norbert Gregorek [ 15 kwi 2011, o 22:33 ]
Tytuł:  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 :)

Autor:  Miłosz Makowski [ 15 kwi 2011, o 23:48 ]
Tytuł:  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.

Strona 1 z 1 Strefa czasowa: UTC + 1 [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/