|
Informatyka UJ forum Rocznik 2005 - czyli najlepsze forum w sieci
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
cct
pijak
Dołączył: 21 Mar 2006
Posty: 202
Przeczytał: 0 tematów
|
Wysłany: Pon 17:06, 18 Gru 2006 Temat postu: Zadania U/V- szybka reprezentacja grafu+ binarki+ generatory |
|
|
Wierzę, że się przydadzą. Powinny generować dobre dane (tj bez powtórzeń etc.), ale w przypadku niezgodności z odpowiedzią można poszukać czy coś przypadkiem nie trafiło się złego.
Wersje windowsowe:
[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]
Wersje linuxowe, kompilowane na Virgo:
[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]
EDIT: jak zauważył Chlebek, moje U nie czyściło do konca pamięci (technicznie rzecz ujmując, w ogóle nie czyściło, i na tym polega cały bajer ;)), ale coś się krzaczyło czasem dla niektórych mniejszych testów, więc poprawiłem metodą brute_memset_na_ilość_elementów nieco binarki. Jakby komuś wyskakiwał ANS to niech porówna jeszcze z nową wersją.
Ostatnio zmieniony przez cct dnia Śro 14:21, 20 Gru 2006, w całości zmieniany 4 razy
|
|
Powrót do góry |
|
|
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
przem
[świeżak]
Dołączył: 13 Paź 2006
Posty: 14
Przeczytał: 0 tematów
Skąd: Krosno
|
Wysłany: Pon 19:58, 18 Gru 2006 Temat postu: |
|
|
dzieki cct na pewno sie przyda
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
chlebek
alkoholik
Dołączył: 04 Lut 2006
Posty: 556
Przeczytał: 0 tematów
Skąd: Siedlce\Kraków
|
Wysłany: Wto 1:24, 19 Gru 2006 Temat postu: |
|
|
dzieki wielkie
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
cct
pijak
Dołączył: 21 Mar 2006
Posty: 202
Przeczytał: 0 tematów
|
Wysłany: Wto 18:21, 19 Gru 2006 Temat postu: |
|
|
Doszły binarki do uruchamiania pod linuxem (na prośbę Insa).
Tymczasem, ponieważ parę osób pytało - szybki opis kursorowej reprezentacji grafu Robsona-ceceta (nazwa od niezależnego odkrycia reprezentacji przez dwóch paranaukowców w początkach XXI wieku ;))
Do trzymania krawędzi wystarczy np. rekordzik:
Kod: | struct TKrawedz{
long skad, dokad, waga ;
} ; // TKrawedx |
1. wczytujemy wszystkie krawędzie do tablicy "krawędzie" - przy czym "wszystkie" oznacza również te dodane przez nas (czyli zwrotne do grafu rezydualnego oraz ew. połączenia za źródłem/ujściem lub podwojenie wierzchołków zależnie od algorytmu i zadania).
Innymi słowy - w tablicy znajdować powinny się wszystkie krawędzie które mogą pojawić się w trakcie działania programu.
Jeśli krawędź istaniała (tj. mieliśmy ją podaną bezpośrednio w danych wejściowych) jej wagę ustawiamy na 1, WPP na 0.
2. sortujemy krawędzie (najlepiej QuickSortem, chyba, że starczy komuś pamięci na CountSorta - zakresy kluczy są dużo mniejsze niż liczba elementów) wg wartości pola "skad"
3. po posortowaniu tablicy tworzymy tablicę count, w której trzymamy szereg numerów komórek, w których znajduje się ostatnie wystąpienie danego klucza w tablicy; innymi słowy:
Kod: | count[ i ] - 1 == numer komórki w tablicy krawędzi, pod którą znajduje się ostatnia krawedź z polem "skad" o wartości i |
4. teraz lista wszystkich następników i-tego węzłą znajduje się w tablicy krawędzi pod numerami od count[ i-1 ] do count[ i ]-1
innymi słowy:
Kod: | // zał. nie istnieje węzeł 0, oraz count[ 0 ] = 0
// pętla "for each nastepnik węzła i do" wygląda
for ( long j = count[ i-1 ] ; i < count[ i ] ; i++ ){
// teraz krawędzie[ j ] == krawędź { i -> krawędzie[ j ].dokad }
} // fora |
Jak widzimy, wszystkie odwołania do następników danego węzła są odwołaniami do sąsiednich komórek tabeli "krawędzie".
Robson sugerował jeszcze, aby w rekordzie trzymać sobie adres do numeru tablicy powrotnej, ale można to równie dobrze później na bieżąco liczyć osobną funkcyjką.
Mam nadzieję, że pomoże osobom które wciąż z TLE na wskaźnikach walczą.
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
Spectro
Mistrz grilla
Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów
Skąd: Kurdwanów
|
Wysłany: Wto 22:03, 19 Gru 2006 Temat postu: |
|
|
cct napisał: | Mam nadzieję, że pomoże osobom które wciąż z TLE na wskaźnikach walczą. |
Ja już nie :P . Jednak od 13.07 mam OK po rejudgu. Czyli to wszystko była wina cache'owania...
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
chlebek
alkoholik
Dołączył: 04 Lut 2006
Posty: 556
Przeczytał: 0 tematów
Skąd: Siedlce\Kraków
|
Wysłany: Śro 13:50, 20 Gru 2006 Temat postu: |
|
|
czy ktos mial problem z RTE w tym zadaniue ?
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
Yoter
zielony żul
Dołączył: 19 Lis 2005
Posty: 1033
Przeczytał: 0 tematów
Skąd: Gościeradów
|
Wysłany: Śro 14:07, 20 Gru 2006 Temat postu: |
|
|
ja - za mało alokowanej pamięci...
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
chlebek
alkoholik
Dołączył: 04 Lut 2006
Posty: 556
Przeczytał: 0 tematów
Skąd: Siedlce\Kraków
|
Wysłany: Śro 14:15, 20 Gru 2006 Temat postu: |
|
|
Yoter napisał: | ja - za mało alokowanej pamięci... |
bardzo smieszne... :( , ale niby glupi pytanie ;/( albo za malo pamieci, albo gdzies wychodzi poza )
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
Spectro
Mistrz grilla
Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów
Skąd: Kurdwanów
|
Wysłany: Śro 14:24, 20 Gru 2006 Temat postu: |
|
|
Ja miałem RTE przez chwilę, ale po zamianie intów na shorty do oznaczania numerów wierzchołków już tego błędu nie było.
Aha, wartość przepływów i przepustowość trzymam w charach, choć można byłoby od biedy obie rzeczy w jednym polu zmieścić :P .
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
chlebek
alkoholik
Dołączył: 04 Lut 2006
Posty: 556
Przeczytał: 0 tematów
Skąd: Siedlce\Kraków
|
Wysłany: Śro 14:42, 20 Gru 2006 Temat postu: |
|
|
poszlo, a jednak blad przy wczytywaniu tego nowego grafu
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
Yoter
zielony żul
Dołączył: 19 Lis 2005
Posty: 1033
Przeczytał: 0 tematów
Skąd: Gościeradów
|
Wysłany: Śro 15:16, 20 Gru 2006 Temat postu: |
|
|
@chlebek : to nie był żart ;p
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
trywialna
pijak
Dołączył: 12 Mar 2006
Posty: 257
Przeczytał: 0 tematów
Skąd: z kontowni:)
|
Wysłany: Czw 15:06, 21 Gru 2006 Temat postu: |
|
|
@cct: czy mi sie zdaje czy twoj generator testów do V (pod windowsem) jest tak naprawde generatorem testow dla U?
edit: wycofuje pytanie
Ostatnio zmieniony przez trywialna dnia Czw 18:11, 21 Gru 2006, w całości zmieniany 1 raz
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
hansu
Nieomylny Admin
Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów
Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?
|
Wysłany: Czw 17:35, 21 Gru 2006 Temat postu: |
|
|
@cct: To badz jeszcze dobrym opensourcowcem i dorzuc kody zrodlowe do tych wszystkich binarek ktore podlinkowales ;P
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
trywialna
pijak
Dołączył: 12 Mar 2006
Posty: 257
Przeczytał: 0 tematów
Skąd: z kontowni:)
|
Wysłany: Czw 17:56, 21 Gru 2006 Temat postu: |
|
|
Ma może ktoś jakieś testy do V? mam ansa...
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
cct
pijak
Dołączył: 21 Mar 2006
Posty: 202
Przeczytał: 0 tematów
|
Wysłany: Czw 22:51, 21 Gru 2006 Temat postu: |
|
|
hansu napisał: | @cct: To badz jeszcze dobrym opensourcowcem i dorzuc kody zrodlowe do tych wszystkich binarek ktore podlinkowales ;P |
A kto powiedział, że jestem opensourcowcem? Bywam altruistą czy społecznikiem, ale tylko jak mam czas i energię.
...a że święta idą, to potraktujcie poniższe dywagacje jako prezent ;)
[Dr Ślusarek rozpisał się o wersji iteracyjnej DFSa w Hopcroft-Karpie z tego co pamiętam, tutaj parę 'luźnych sugestii' co do wersji rekurencyjnej, która śmiga, że aż pamięć trzeszczy na mrozie.]
Kod: | DFS( long wezel, long minimum )
visited[ wezel ] = true
// jesli dochodzimy do ujscia to zaczynamy wychodzic
if ( wezel == stop )
struzka = minimum
wychodzenie = true
return
for each v in L[ wezel ] w rezydualnym do
// jesli bylismy na wierzcholku, lub przeplyw za maly, to pomijamy
if ( visited[ v ] ) or ( przeplywWRezydualnym( wezel, v ) <= 0 )
continue // dla tej krawedzi nic nie robimy
// wchodzac bierze MIN z minimum jakim doszlismy oraz tego po czym idziemy
DFS( v, MIN( minimum, przeplywWRezydualnym( wezel, v ) ) )
// jesli juz widzielismy ujscie, to poprawiamy oszacowania i wychodzimy
if ( wychodzenie )
// poprawiamy oszacowanie sieci rezydualnej:
// 1. zmniejszamy ilosc mozliwa do puszczenia przez sciezke,
// po ktorej przydreptalismy
// 2. zwiekszamy mozliwosc manewru (puszczenia wody) w druga strone
przeplywWRezydualnym( wezel, v ) -= struzka
przeplywWRezydualnym( v, wezel ) += struzka
return // awaryjne wyjscie z DFSa
end DFS . |
Ta procedurka załatwia praktycznie oba zadanka. Graf rezydualny tworzymy przy wczytywaniu oczywiście, i DFSa zapuszczamy już w nim samym. A jak długo go zapuszczamy i inne detale wokół tej procedurki już sobie naprawdę każdy sam dopracuje - inaczej ten świąteczny prezent wyszedłby przesłodzony :P
Zresztą, i tak mi pewnie już TCS nalicza ujemne punkty od jakiegoś czasu ;)
Ostatnio zmieniony przez cct dnia Pią 2:48, 22 Gru 2006, w całości zmieniany 1 raz
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
Rogal
Zjeb z kaszanką
Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów
Skąd: koło podbiegunowe
|
Wysłany: Pią 0:14, 22 Gru 2006 Temat postu: |
|
|
Hmmm może się nie znam i co prawda nie byłem na wykładzie, ale tak na pierwszy rzut oka DFS nie wydaje mi się najlepszym pomysłem. BFS powinien sprawdzić się znacznie lepiej.
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
dzendras
Germański oprawca
Dołączył: 07 Mar 2006
Posty: 1326
Przeczytał: 0 tematów
Skąd: Chorzów
|
Wysłany: Pią 0:19, 22 Gru 2006 Temat postu: |
|
|
Rogal: Nam p. Jeżabek mówił, że do zadań U i V wystarczy DFS i co ważne będzie to szybsze od wersji z BFS. Bez BFS nie obejdzie się za to w zadaniu Z2.
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
Spectro
Mistrz grilla
Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów
Skąd: Kurdwanów
|
Wysłany: Pią 0:33, 22 Gru 2006 Temat postu: |
|
|
I nic dziwnego:
W standardowej wersji metoda Forda-Fulkersona działa w czasie O(m*|f|), a ponieważ przepustowość każdej krawędzi wynosi co najwyżej 1, to |f| = n, zatem czas: O(m*n). To trochę lepiej niż O(m^2*n) z wersji Edmondsa-Karpa :P .
edit: Trochę głupot tu napisałem ;] .
Ostatnio zmieniony przez Spectro dnia Pią 10:32, 22 Gru 2006, w całości zmieniany 1 raz
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
Rogal
Zjeb z kaszanką
Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów
Skąd: koło podbiegunowe
|
Wysłany: Pią 1:21, 22 Gru 2006 Temat postu: |
|
|
Spectro: Nie mąć ludziom w głowach proszę bo pytanie o złożoność czegoś takiego z BFS-em może pojawić się na egzaminie.
edited: Żeby nie było złożoność zarówno BFS-a jak i DFS-a w tym przypadku to po prostu O(m*|f|) gdzie |f| oznacza maksymalny przepływ, a że przepustowość każdej krawędzi jest jednostkowa i ścieżek jest na pewno mniej niż wierzchołków (w obu zadaniach) to złożoność jest O(mn).
edited2: Żeby było jeszcze jaśniej Edmonds-Karp na takich szczególnych grafach jak te które mamy w tym zadaniu działa w czasie O(mn) a nie żadne O(m^2*n) jak raczył napisać Spectro :wink:
edited3: Teraz to już się pewnie czepiam, ale Cytat: | a ponieważ przepustowość każdej krawędzi wynosi co najwyżej 1, to |f| = n | w ogólności nie jest prawdą, oznacza tylko, że |f|<=m
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
cct
pijak
Dołączył: 21 Mar 2006
Posty: 202
Przeczytał: 0 tematów
|
Wysłany: Pią 2:55, 22 Gru 2006 Temat postu: |
|
|
Rogal napisał: | Hmmm może się nie znam i co prawda nie byłem na wykładzie, ale tak na pierwszy rzut oka DFS nie wydaje mi się najlepszym pomysłem. BFS powinien sprawdzić się znacznie lepiej. |
Ludzie dostawali TLE na BFSie, które znikało po przerobieniu na DFSa, więc raczej pozwolę się nie zgodzić. :)
Ogółem, to np. w takim V BFS obejrzy dokładnie wszystkie osiągalne ze źródła wierzchołki zanim dojdzie do ujścia (które ma największą odległość od S), a w DFSie co najwyżej wszystkie (jakkolwiek by to trywialnie nie brzmiało, tak właśnie jest :)) - więc BFS nie będzie lepszy, może być co najwyżej równy lub gorszy. QED. (Aha - statystycznie - będzie bardzo silnie gorszy).
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
hansu
Nieomylny Admin
Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów
Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?
|
Wysłany: Pią 3:24, 22 Gru 2006 Temat postu: |
|
|
cct ma racje - w tym szczegolnym przypadku DFS bedzie wydajniejszy od BFSa, wprawdzie tylko o stala, ale i tak dosc istotnie.
Natomiast w ogolnym przypadku algorytmu EK dla dowolnej sieci przeplywowej DFS jest mocno chybionym pomyslem, bo w EK potrzebujemy wybrac najkrotsza sciezke od zrodla do ujscia i takie wlasnie postepowanie gwarantuje nam ze ze iteracji petli zwiekszajacej wartosc przeplywu bedzie EV a nie |f|, jak to jest w ogolnym przypadku metody Forda-Fulkersona. Natomiast tutaj, dzieki temu ze |f| <= V, mozemy uzyc dowolnej z tych metod a i tak nie wyjdziemy asymptotycznie poza EV. No ale tak jak napisal cct DFS jest wydajniejszy...
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
Spectro
Mistrz grilla
Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów
Skąd: Kurdwanów
|
Wysłany: Pią 10:31, 22 Gru 2006 Temat postu: |
|
|
Rogal napisał: | Nie mąć ludziom w głowach proszę bo pytanie o złożoność czegoś takiego z BFS-em może pojawić się na egzaminie. |
Wiem już, że mi się pomieszało. Jak zwykle byłem półprzytomny :/ .
Rogal napisał: | Teraz to już się pewnie czepiam, ale Cytat: | a ponieważ przepustowość każdej krawędzi wynosi co najwyżej 1, to |f| = n | w ogólności nie jest prawdą, oznacza tylko, że |f|<=m |
Tej ostatnia równość jest wzięta chyba z kosmosu, bo nie znajduję dla niej żadnego uzasadnienia. Mówimy dalej o przepływie binarnym? W takim razie |f| = O(n), doprecyzowując to, co napisałem wcześniej (i to akurat była prawda).
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
Rogal
Zjeb z kaszanką
Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów
Skąd: koło podbiegunowe
|
Wysłany: Pią 11:16, 22 Gru 2006 Temat postu: |
|
|
Spector: Eeee dobra, co do ostatniego masz rację - w tym przypadku to ja byłem półprzytomny :D
Pomyliło mi się z przypadkiem, gdy pomiędzy daną parą wierzchołków może być więcej niż jedna krawędź - ale wtedy możemy z tych kilku krawędzi zrobić przecież jedną, która ma przepsutowość > 1.
cct: Tyż prawda, że akurat w zad. V DFS zadziała lepiej. Nie mniej graf w V to już jest tak szczególny, że tutaj wogóle nie powinno się stosować przepływu tylko H-K i dlatego takie cuda przechodzą. Natomiast w U wydaje mi się, że BFS powinien działać lepiej, nie mniej trzebaby przeprowadzić szereg testów.
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
Spectro
Mistrz grilla
Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów
Skąd: Kurdwanów
|
Wysłany: Pią 12:19, 22 Gru 2006 Temat postu: |
|
|
Rogal napisał: | Tyż prawda, że akurat w zad. V DFS zadziała lepiej. |
Tak, to akurat łatwo sobie wyobrazić, bo odległość od źródła do ujścia jest niewielka w stosunku do hmm... rozpiętości sieci ;) .
Rogal napisał: | Natomiast w U wydaje mi się, że BFS powinien działać lepiej, nie mniej trzebaby przeprowadzić szereg testów. |
Moja pierwsza wersja algorytmu do U miała właśnie BFSa i bardzo szybko dostawała TLE. Domyślam się, że testy, który wywalały tę metodę, były podobne do tych z V. A jaki test mógłby wywalić DFSa? Taki, w którym byłyby duże różnice między poszczególnymi przepustowościami krawędzi, względnie przepustowości nie byłyby całkowite. W zadaniu U taka sytuacja się raczej nie zdarzy ;] .
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
Rogal
Zjeb z kaszanką
Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów
Skąd: koło podbiegunowe
|
Wysłany: Pią 12:59, 22 Gru 2006 Temat postu: |
|
|
Spectro: Łatwo zrobić, żeby BFS działał w czasie zupełnie pesymistycznym. Wystarczy graf 2-dzielny z podpiętym źródłem i ujściem (taki jak w zad V) albo nawet ogólniej - graf k-dzielny - czyli taki podzielony na kilka warstw - przy czym każda warstwa jest połączona krawędziami tylko z poprzednią (w szczególności ze źródłem) i następną (w szczególności z ujściem). Wtedy każda ścieżka ma długość k+1 i za każdym razem przeglądane są wszystkie wierzchołki (czy tam prawie wszystkie :wink: )
Natomiast przypadek pesymistyczny dla DFS-a zależałby nie tylko od samej struktury grafu ale przede wszystkim od tego w jakiej kolejności w wierzchołku pamiętane są poszczególne krawędzie. Tak więc generalnie gdyby krawędzie ustawić w porządku losowym (albo może sortowanie coś pomoże?) to o przypadek pesymistyczny bardzo trudno (jak np. dla QuickSorta)
Nie mniej jednak idea wyszukiwania najkrótszej ścieżki podoba mi się znacznie bardziej niż wyszukiwania ścieżki losowej :D A wogóle to imho najprzyjemniejsze jest szukanie najszerszej ścieżki korzystając z Dijkstry, no ale to już też jest inna para kaloszy.
|
|
Powrót do góry |
|
|
|
|
Nie możesz pisać nowych tematów Nie możesz odpowiadać w tematach Nie możesz zmieniać swoich postów Nie możesz usuwać swoich postów Nie możesz głosować w ankietach
|
fora.pl - załóż własne forum dyskusyjne za darmo
Powered by phpBB © 2001, 2005 phpBB Group
|