Transport

Dzisiaj rozwiążemy zadanie „na przepływ”. Na pierwszy (a może nawet i na trzeci) rzut oka nie widać w nim żadnej trudności: dostajemy silnie spójny graf skierowany, w którym niektóre wierzchołki są źródłami (z podanym zaopatrzeniem), a niektóre ujściami (z podanym zapotrzebowaniem). Naszym zadaniem jest dobranie przepływów na krawędziach tak, aby wysycić wszystkie żądania. Cała sytuacja wydaje się jednak o tyle prosta, że przepustowość każdej krawędzi jest taka sama i równa sumarycznemu zaopatrzeniu. Można więc pomyśleć, że w takim razie dobranie przepływów na krawędziach nie powinno przysparzać żadnych problemów! Jeśli jednak popatrzymy na ranking zawodów, z których pochodzi to zadanie, okaże się, że nie rozwiązała go żadna z (bardzo dobrych) drużyn. Może więc nie jest ono takie całkiem proste?

Warto dodać, że zadanie pochodzi z Andrew Stankevich Contest 29 (oryginalną treść można zobaczyć patrząc na zadanie G tutaj). Co samo w sobie jest niezłą rekomendacją! Zanim zabierzemy się za rozwiązywanie zauważmy, że podany graf skierowany jest dość spory, bo aż na n\leq 10^5 wierzchołkach i m\leq 10^5 krawędziach. Ponadto maksymalne zapotrzebowania i zaopatrzenia wydają się być dobrane tak, żeby ich suma nie przekraczała 10^9 (a na pewno są dobrane tak, aby sumaryczne zapotrzebowanie było równe sumarycznemu zaopatrzeniu).

Może warto zacząć od zastanowienia się, dlaczego zadanie mogłoby wydawać się proste. Skoro cały graf jest silnie spójny, możemy wybrać dowolne źródło i dowolne ujście, a następnie znaleźć łączącą je ścieżkę. Teraz jeśli aktualne zaopatrzenie źródła to a, a aktualne zapotrzebowanie ujścia to b, możemy przesłać tą ścieżką \min(a,b) jednostek, a następnie zmniejszyć zaopatrzenie źródła i zwiększyć zapotrzebowanie ujścia o \min(a,b). Łatwo zobaczyć, że przynajmniej jedna z tych wielkości stanie się wtedy równa zeru, czyli pozbyliśmy się jednego źródła lub jednego ujścia. Kontynuując taką procedurę prędzej lub później doprowadzimy więc do sytuacji, w której nie ma już żadnego źródła ani żadnego ujścia. Co więcej, równie łatwo zauważyć, że sumaryczny przepływ przez żadną krawędź w żadnym wypadku nie przekroczy sumy zaopatrzeń (równej sumie zapotrzebowań). Co daje nam dowód, że (o ile tylko graf jest silnie spójny) zawsze da się wysycić wszystkie żądania, oraz proste w implementacji rozwiązanie.

Które jest oczywiście zbyt wolne. W najgorszym wypadku potrzebujemy bowiem n iteracji. Każda z nich sprowadza się do znalezienia ścieżki między dwoma wierzchołkami w grafie skierowanym, na co potrzebujemy pewnie \mathcal{O}(m) operacji. Czyli sumaryczna złożoność to \mathcal{O}(nm), a to przecież strasznie dużo. Co zrobić?

Mamy dwie możliwości: albo zmniejszymy liczbę iteracji, albo przyśpieszymy znajdowanie ścieżki łączącej dwa wierzchołki. To pierwsze wydaje się raczej trudne, spróbujmy więc opcji numer dwa. Ta też nie wydaje się bardzo prosta, więc może uprośćmy sobie życie zamieniając graf skierowany na (spójny) nieskierowany. Życie staje się wtedy o tyle łatwe, że tak naprawdę nie potrzebujemy rozważać wszystkich krawędzi: wystarczy nam wybranie (dowolnego) drzewa rozpinającego. Oczywiście krawędzie takiego drzewa wystarczają, aby znaleźć ścieżkę łączącą dwa dowolne wierzchołki u i v. Co więcej, nietrudno jest wygenerować taką ścieżkę. Trzeba tylko ukorzenić drzewo (powiedzmy, że w wierzchołku 1), a następnie znaleźć najniższego wspólnego przodka \textrm{lca}(u,v) wierzchołków u i v. Szukana ścieżka składa się wtedy z dwóch części: najpierw idziemy z u w górę aż do \textrm{lca}(u,v), a następnie z \textrm{lca}(u,v) w dół aż do v. Oczywiście może być tak, że cała ścieżka jest dość długa, więc niekoniecznie stać nas na jawne wygenerowanie jej krawędzi. Jednak nie jest to konieczne, gdyż ostatecznie interesuje nas tylko finalny przepływ na każdej krawędzi. Tak naprawdę musimy więc tylko zwiększyć przepływ na wszystkich krawędziach należących do ścieżki o pewną wartość, a co nawet lepsze wcale nie musimy cały czas przechowywać w jawny sposób tych wszystkich aktualnych przepływów. W zupełności wystarczy nam gwarancja, że takie aktualne przepływy będą znane dopiero na samym końcu. Można więc skorzystać z następującej sztuczki: dla każdego wierzchołka u przechowujemy akumulator \Delta_u. Aby zwiększyć aktualny przepływ na ścieżce od u do \textrm{lca}(u,v) o C, zwiększamy \Delta_u o C oraz zmniejszamy \Delta_{\textrm{lca}(u,v)} o C. Dzięki temu zachowany jest następujący niezmiennik: aktualny przepływ przez krawędz z u do jego ojca w drzewie jest równy sumie wszystkich \Delta_v w poddrzewie zakorzenionym w u. Takie sumy można łatwo wyznaczyć w czasie \mathcal{O}(n) na samym końcu, a zwiększenie przepływu sprowadza się do kilku prostych operacji arytmetycznych. No prawie: musimy znać \textrm{lca}(u,v). Nie jest jednak trudno wyznaczy najniższego wspólnego przodka w czasie \mathcal{O}(\log n), można i szybciej (jak pewnie wiecie).

Ekstra, ale przecież nasz graf jest skierowany. Może jednak dałoby się jakoś uogólnić opisaną wyżej sztuczkę? Korzystając z założenia o silnej spójności możemy znaleźć nie jedno, lecz dwa drzewa zakorzenione w wierzchołku 1. W pierwszym z nich (nazwijmy je drzewem w górę) krawędzie skierowane są z wierzchołka do ojca, a w drugim (nazwijmy je drzewem w dół) odwrotnie. Każdy wierzchołek występuje w obydwu drzewach, no i można je skonstruować dwukrotnie przeszukując w głąb graf zaczynając z wierzchołka 1 (raz zgodnie z kierunkiem krawędzi, a raz wręcz przeciwnie). Dla przykładu z treści pewnie uzyskamy drzewa oznaczone na czerwono i zielono na poniższej ilustracji.

transport

Teraz od razu widać, że takie dwa drzewa w zupełności wystarczą, żeby znaleźć skierowaną ścieżkę z dowolnego u do dowolnego v. Wystarczy tylko pójśc w drzewie w górę z u do korzenia, a następnie w drzewie w dół z korzenia do v. Czyli koniec?

No nie, nie koniec. Może się bowiem zdarzyć (jak zresztą widać na ilustracji), że niektóre krawędzie należą do obydwu drzew. W związku z tym może się zdarzyć, że znaleziona ścieżka nie jest prosta, a co za tym idzie zwiększymy przepływ przez niektóre krawędzie nie o C, lecz o 2C. A to z kolei oznacza, że być może przekroczymy ich przepustowości. Czyli kiepsko.

Może jednak nie całkiem kiepsko? Wystarczy przecież znaleźć na ścieżce w górę z u pierwszy wierzchołek u', który pojawia się także na ścieżce w dół do v. Następnie możemy pójść z u w górę do u', i dalej z u' w dół do v. Łatwo się przekonać, że skonstruowana w ten sposób ścieżka będzie prosta, co gwarantuje, że nie przekroczymy dozwolonych przepustowości. Znając u' możemy zastosować dokładnie taką samą sztuczkę jak wcześniej by w niejawny sposób reprezentować aktualny przepływ na każdej krawędzi (przy czym tym razem należy zastosować tę sztuczkę dwukrotnie: raz na drzewie w górę i raz na drzewie w dół). Czyli zredukowaliśmy cały problem do wyznaczenia u'.

Nie wydaje się jednak, że to już koniec. Tym niemniej zredukowaliśmy problem do następującego: mamy dane dwa drzewa T i T^r na takim samym zbiorze n wierzchołków oraz zbiór pytań. W każdym pytaniu dostajemy dwa wierzchołki u i v, i musimy znaleźć pierwszy wierzchołek na ścieżce z u do korzenia w T, który pojawia się (gdziekolwiek) na ścieżce z v do korzenia w T^r. Dodatkowo możemy założyć, że w obydwu drzewach 1 jest korzeniem. Czyli udało nam się całkiem pozbyć przepływów i zredukować całe sytuację do przyjemnie wyglądającego zadania dotyczącego drzew. A przecież drzewa są proste, prawda?

No może i są proste, ale w tym przypadku nie jest tak całkiem łatwo. Ale może nie jest też bardzo trudno? Zauważmy najpierw, że wcale nie musimy odpowiadąc na pytania w takiej samej kolejności, w jakiej były zadawane. Cały problem jest więc offline, co zwykle istotnie upraszcza rozwiązanie. Spróbujmy więc rozważyć jednoczesnie wszystkie pytania z takim samym v. Powiedzmy, że dla każdego v', który jest jego przodkiem, zaznaczamy odpowiadający mu wierzchołek T. Wtedy dla każdego pytania (u,v) musimy tylko znaleźć najniższego zaznaczonego przodka u w T. Zastanówmy się wiec, jak zmienia się zbiór zaznaczonych wierzchołków podczas rozważania kolejnych v. Jeśli rozpatrujemy je w dowolnej kolejności, pewnie ciężko powiedzieć na ten temat coś sensownego, ale przecież tylko od nas zależy, jaką kolejność wybierzemy! Możemy więc rozpatrywać kolejne v przeszukując T^r w głąb. Wtedy w kolejnych krokach (których w sumie będzie 2n) musimy tylko zaznaczyć lub odznaczyć jeden wierzchołek v, a ponadto czasami musimy znaleźć najniższego zaznaczonego przodka podanego wierzchołka u.

Zredukowaliśmy więc całe zadanie do skonstruowania efektywnej struktury danych, w której możemy przechowywać drzewo na n wierzchołkach. Struktura powinna pozwalać na zaznaczanie i odznaczanie wierzchołków, oraz na znajdowanie najniższego zaznaczonego przodka podanego wierzchołka. Spróbujemy zaimplementować te wszystkie operacje w czasie \mathcal{O}(\log n). Zauważmy najpierw, że jest to dość łatwe jeśli nasze drzewo jest mniej więcej zrównoważone, gdyż każdy wierzchołek ma wtedy niewielu przodków. Możemy ich więc naiwnie przejrzeć. Niestety, nie każde drzewo jest zrównoważone.

Zastosujmy więc w miarę standardowy trik: zrównoważmy nasze drzewo! Jedną z możliwych terapii jest wybranie niektórych krawędzi tak, aby całe drzewo rozpadło się na zbiór wierzchołkowo rozłącznych ścieżek, z których każda zaczyna się w pewnym wierzchołku i idzie w górę, tak jak na poniższym rysunku.

transport1

Ponadto chcielibyśmy, aby nad dowolnym wierzchołkiem było tylko \mathcal{O}(\log n) ścieżek, lub inaczej mówiąc cały zbiór jego wierzchołków dał się przedstawić jako suma prefiksów \mathcal{O}(\log n) ścieżek. Nie jest to trudne: wystarczy bowiem wybrać dla każdego wierzchołka krawędź prowadzącą do największego dziecka. Taka własność jest wygodna dlatego, że wtedy szukając najniższego zaznaczonego przodka danego wierzchołka możemy sobie śmiało pozwolić na przeiterowanie po wszystkich ścieżkach, których prefiksy reprezentują cały interesujący nas zbiór. Czyli teraz wystarczy tylko dla każdej takiej ścieżki przechowywać zaznaczone wierzchołki tak, aby można było szybko wybrać najniższego zaznaczonego przodka na ścieżce. Inaczej mówiąc, zredukowaliśmy problem na drzewie do problemu na ścieżce.

Teraz jest już łatwo. Można na przykład przechowywać numery preorder wszystkich zaznaczonych wierzchołków na danej ścieżce w strukturze typu set. Pozwoli to na zaznaczanie i odznaczanie wierzchołków w czasie \mathcal{O}(\log n) (gdyż każdy z nich należy do dokładnie jednej, być może zdegenerowanej, ścieżki). Zaś szukanie najniższego zaznaczonego przodka sprowadza się do znalezienie poprzednika w zbiorze liczb, co znów można wykonać w czasie \mathcal{O}(\log n). Niestety tę drugą operację należy być może powtórzyć na każdej ścieżce powyżej naszego u, co daje nam sumaryczny czas odpowiedzi na jedno pytanie równy \mathcal{O}(\log^2n). Dość łatwo jednak zmniejszyć ten czas do \mathcal{O}(\log n) i uzyskać rozwiązanie, które działa w sumarycznym czasie \mathcal{O}(n\log n). Dopracowanie tego szczegółu pozostawiam jednak Czytelnikowi.

Reklamy

2 myśli nt. „Transport

  1. Nie wiem czy dobrze zrozumiałem, ale chyba tylko od nas zależy, które źródło chcemy sparować z którym celem. Ten dodatkowy stopień (naszej) swobody, może być może jakoś nam pomóc w tym, by zapytania do tych dwóch drzew były dla nas łatwiejsze, albo wręcz by drzewa były milsze? W ogóle tak teraz się nad tym ciutkę zastanawiam, bo chyba w ogóle przemilczałeś kwestię jak te źródła i cele dobrać w pary — domyślam się, że są sposoby głupsze i lepsze, tj. owocujące większą bądź mniejszą liczbą zapytań?

  2. To parowanie można robić lepiej lub gorzej, ale tak czy inaczej otrzymamy między n a 2n pytań. Być może ma sens zadawanie pytań patrząc na drzewa, ale nie widzę jak dokładnie należałoby to robić (zresztą rozwiązując zadanie szczerze mówiąc spodobał mi się ten podproblem z drzewami, więc już nie próbowałem ulepszać redukcji).

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s