OIG - Magazyny

[argv]

Mam problem z tym zadaniem:

Czy ktoś może je robił i może króciutko opisać algorytm? Moja pierwsza próba polegała na wrzuceniu potencjalnych miast z ktorych moge cos rozwiezc do kolejki, delminowac je i zapuszczac bfsa rozwozacego towary (w ten sposob odwiedzam zawsze najkrotsze). Niestety strategia chyba jest bledna, a zreszta zasoby pamieciowe i czasowe jakie pochlania i tak nie mieszcza sie w zadnych normach obyczajowych
Uwaga: zadanie jest raczej proste

Prosze o jakas podpowiedz

[Afish]

Jeżeli dobrze zrozumiałem treść zadania, to zauważ, że nie jest istotne, z którego miasta do którego będziemy transportowali towary (bo między każdą parą miast jest tylko jedna ścieżka). Przy czym jeżeli w jakimś mieście jest już odpowiednia liczba towarów, to tego miasta nie ruszamy, a do danego miasta dostarczamy towary z najbliższego, które ma nadwyżkę. Zatem jeżeli weźmiesz drogę łączącą dwa sąsiednie miasta, to musisz policzyć dla niej, jak dużo towarów przez nią należy przetransportować. A to jesteśmy w stanie policzyć zapuszczając raz DFSa.
Jeżeli nagadałem głupot, to bardzo przepraszam

[argv]

Hmm z tym dfs podrzuciles mi pewien pomysl Boje sie czy w jakis wrednych przypadkach mimo wszystko nie znajde optymalnego kosztu, ale przemysle, ogarne to jakos i zobacze co z tego wyjdzie

[Dumel]

chciałem to wysłać wczoraj ale coś forum szwankowało:
nie da sie uniknąć kosztu transportu towaru z/do liści. nie musisz dbać o kolejność przemieszczania towarów. przykładowo masz w liściu 0 i w jego rodzicu 0 a musisz mieć wszędzie 2. możesz teraz przenieść 2 do liścia, w rodzicu zostawiając -2. ta brakująca dwójka i tak prędzej czy później pojawi się tam gdzie powinna wiec tylko wcześniej w ten sposób "zaksięgowaliśmy" to przejście. po tym spostrzeżeniu ukazuje sie taki algorytm:
wrzucamy do jakiejś wydajnej strukturki (stlowa priority-queue, moze byc tez np. kopiec) wierzchołki drzewa. porównujemy je według stopni, dodatkowo pamiętamy ilość towaru i wskaźnik do rodzica (wcześniej informacje o rodzicach dostajemy np. z bfs-a). teraz za każdym razem ciągniemy wierzchołek o najniższym stopniu (liść) przerzucamy odpowiednią ilość towaru z/do rodzica, usuwamy ten wierzchołek i aktualizujemy dane w rodzicu
zlożoność: \(\displaystyle{ O(n \ ln n)}\)
można też zrobić w O(n). na początku wczucamy na stos wszystkie liście. usuwamy je po kolei, aktualizujemy stopnie rodziców, gdy po aktualizacji jest on =1 to wrzucamy go na stos.


dowód poprawności tego algorytmu pewnie jest łatwiutki, bo poprawność jest dość intuicyjna

[argv]

Dzieki za szczegołowy opis - podoba mi sie ten pomysl z "ksiegowaniem"
Dopiero od miesiaca bawie sie w takie zadanka (wieczory sie dluza) i nie mam jeszcze wprawy w ich weryfikowaniu wiec dam znac jak ogarne to dokladniej. Na uczelni jak sie pojawialy takie zadanka to zwykle ktos wymyslil algorytm no i sie pisalo, a jak trzeba kombinowac samemu i jeszcze miescic sie w ograniczeniach to jest duuuzo trudniej No ale mam nadzieje ze z czasem sie wyrobie

Jeszcze raz wielkie dzieki - dam znac co sie z tego urodzilo