![]() |
||
Wojciech Guzicki (treść, opracowanie) Tomasz Waleń (program wzorcowy) Gdzie zbudować browar?Mieszkańcy bajtockiej wyspy Abstynencja bardzo lubią piwo bezalkoholowe. Do tej pory piwo bezalkoholowe sprowadzano z Polski, ale w tym roku w jednym z miast na Abstynencji zostanie wybudowany browar. Wszystkie miasta wyspy leżą na wybrzeżu i są połączone autostradą obiegającą wyspę wzdłuż brzegu. Inwestor budujący browar zebrał informacje o zapotrzebowaniu na piwo, tj. ile cystern piwa trzeba codziennie dostarczyć do każdego z miast. Dysponuje także zestawieniem odległości pomiędzy miastami. Koszt transportu jednej cysterny na odległość 1 km wynosi 1 talar. Dzienny koszt transportu to suma, jaką trzeba wyłożyć, by do każdego miasta przetransportować z browaru tyle cystern, ile wynosi zapotrzebowanie w danym mieście. Jego wielkość zależy od miejsca położenia browaru. Inwestor chce zminimalizować koszty transportu piwa. ZadanieNapisz program, który:
WejścieW pierwszym wierszu pliku tekstowego BRO.IN jest zapisana jedna liczba
całkowita n równa liczbie miast, WyjścieTwój program powinien zapisać w pierwszym i jedynym wierszu pliku tekstowego BRO.OUT, dokładnie jedną liczbę całkowitą równą minimalnemu dziennemu kosztowi transportu piwa. PrzykładDla pliku wejściowego BRO.IN6 1 2 2 3 1 2 5 2 1 10 2 3poprawną odpowiedzią jest plik wyjściowy BRO.OUT 41 RozwiązanieOczywiste rozwiązanie polega na obliczeniu kosztu transportu z każdego miasta do każdego innego i dodaniu otrzymanych liczb. Dla każdego miasta należy obliczyć w tym celu n-1 odległości, co powoduje, że złożoność tego algorytmu wynosi Warto zauważyć, że jeśli miasta są połączone siecią dróg będącą drzewem, to właściwa lokalizacja browaru nie zależy od odległości między miastami, ale tylko od zapotrzebowań w miastach. Oczywiście łączny koszt transportu zależy od odległości. Przypadek, gdy graf dróg jest drzewem (zresztą bardzo prostym), był już tematem jednego z zadań olimpijskich (Mudstok Bis, II Olimpiada Informatyczna, zobacz [2]). Jeśli graf dróg zawiera cykle, odpowiedź jest znacznie bardziej skomplikowana. Dla jednego cyklu istnieje algorytm liniowy, przy czym nie tylko łączny koszt, ale i lokalizacja browaru zależy teraz również od odległości. Trudność polega na tym, że w drzewie istnieje tylko jedna droga prowadząca z danego miasta do każdego innego, natomiast w przypadku miast położonych na okręgu zawsze są dwie drogi: można obiegać okrąg w kierunku zgodnym z ruchem wskazówek zegara lub w kierunku przeciwnym. W przypadku każdej pary miast musimy zdecydować, który kierunek jest bardziej opłacalny. Przyjmijmy dla ustalenia uwagi, że miasta są numerowane w kierunku zgodnym z ruchem wskazówek zegara. Wczytane dane umieszczamy w dwóch tablicach: z[i] jest zapotrzebowaniem na piwo w mieście i, d[i] jest odległością od miasta i do następnego. W algorytmie optymalnym najpierw obliczamy koszt transportu z miasta o numerze 1 (w programie wzorcowym dla wygody rozpoczęto numerację miast od zera; łatwiej wtedy obliczyć numer następnego i poprzedniego miasta na okręgu za pomocą funkcji mod). Jednocześnie obliczamy kilka wielkości pomocniczych:
![]() ![]() Patrzymy na odległość d[r] między miastem r i następnym leżącym na prawo (czyli zgodnie z ruchem wskazówek zegara) miastem l. Jeśli d_l>d_r+d[r], to do miasta o numerze l opłaca się teraz jechać w prawo. A więc dokonujemy kolejnej korekty: zwiększamy dr o d[r] i zr o z[r+1], zmniejszamy dl o d[l] i zl o z[l], zwiększamy o 1 numery miast r i l (pamiętając, że za n+1 bierzemy 1) i wreszcie odpowiednio modyfikujemy łączny koszt transportu. Teraz znów sprawdzamy, czy w podobny sposób nie przesunąć granicy między kierunkami w lewo i w prawo do następnego miasta. Postępujemy tak dotąd, aż dalsze zmiany nie przyniosą korzyści. W ten sposób zakończyliśmy korekty i mamy obliczony łączny koszt transportu piwa z miasta o numerze i. Porównujemy go z dotychczasowym minimalnym zapamiętując, jeśli jest mniejszy, i przechodzimy do kolejnego miasta. Jaka będzie złożoność obliczeniowa tego algorytmu? Dla każdego miasta i dokonywaliśmy najpierw pewnej ustalonej liczby zmian, a następnie w pętli dokonywaliśmy być może wielu korekt. Zauważmy jednak, że każda z tych korekt dotyczyła zawsze nowej granicy między kierunkiem lewym i prawym, przy czym ta granica przesuwała się zawsze tylko w prawo. Zatem łącznie dokonaliśmy tylko n takich korekt. Stąd wynika, że czas działania tego algorytmu będzie proporcjonalny do n. Dla liczby n=10000 różnica w czasie działania obu algorytmów (pierwszego o złożoności TestyDo sprawdzania rozwiązań zawodników użyto 17 testów. Testy 1 i 2, 3 i 4, 5 i 6, 14 i 15 były grupowane. ![]() |