Omówienie zadania Wyjścia ewakuacyjne (III etap XXXI OI)

Drzewo

Plan budynku będziemy przedstawiać jako graf: pomieszczenia to wierzchołki grafu, a korytarze to krawędzie między nimi. Warunek z treści zadania, że pomiędzy każdą parą pomieszczeń można przejść bez zawracania na dokładnie jeden sposób, oznacza, że graf jest drzewem.

Ponadto, rozwiązując to zadanie warto myśleć o drzewie ukorzenionym. Wybór korzenia nie ma znaczenia; możemy przyjąć, że korzeniem drzewa będzie wierzchołek numer \(n\).

Podzadanie 1 — ścieżka

Zastanawiając się nad tym, jak najlepiej rozmieścić wyjścia na ścieżce, łatwo przekonać się o poprawności podejścia zachłannego. Ścieżkę będziemy analizować od jednego z końców, powiedzmy od dołu, czyli od wierzchołka numer \(1\). Początkowo kierujemy ludzi w górę, tak długo jak się da. Gdy już dalej iść nie mogą (zrobiło się ich więcej niż przepustowość kolejnej krawędzi), to budujemy wyjście ewakuacyjne. Następnie bierzemy jak najwięcej kolejnych wierzchołków i kierujemy przebywających w nich ludzi w dół, do właśnie zbudowanego wyjścia; przerywamy, gdy dodanie osób z kolejnego wierzchołka spowodowałoby przekroczenie przepustowości którejś z krawędzi. Powtarzamy wówczas te same czynności z kolejnym wyjściem: kierujemy ludzi w górę, budujemy wyjście, kierujemy ludzi w dół, itd. Tym sposobem kolejne wyjścia stawiamy najwyżej jak to możliwe, uzyskując na koniec najmniejszą możliwą liczbę wyjść. Nietrudno zaimplementować opisane tu podejście zachłanne w czasie liniowym względem długości ścieżki; dopracowanie szczegółów pozostawiamy jako ćwiczenie, a tymczasem przechodzimy do kolejnego podzadania.

Podzadanie 2 — same jedynki

W drugim podzadaniu, w każdym wierzchołku przebywa jedna osoba, a każda krawędź ma przepustowość \(1\). Wówczas, jeśli w jakimś wierzchołku \(v\) nie ma wyjścia, to musi być wyjście w jednym z jego sąsiadów: jeśli nie, to osoba z \(v\) musiałaby najpierw przejść do jakiegoś sąsiada \(u\), a następnie wraz z osobą z \(u\) musiałaby iść dalej w stronę wyjścia — jednak żadna z krawędzi nie mieści dwóch osób. Jest też odwrotnie: jeśli wyjścia rozmieścimy tak, że każdy wierzchołek \(v\) albo ma wyjście, albo ma sąsiada z wyjściem (do którego możemy skierować osobę z \(v\)), to warunki zadania będą spełnione. Musimy więc znaleźć najmniejszy taki zbiór wierzchołków, że każdy wierzchołek albo do niego należy, albo ma w nim sąsiada (na marginesie: zbiór o tej własności nazywany jest zbiorem dominującym).

Jak możemy szukać takiego zbioru? Tutaj podejście zachłanne również działa. Będziemy analizować wierzchołki drzewa w kierunku od liści do korzenia. Jeśli rozważany wierzchołek \(v\) ma dziecko, który ani sam nie ma wyjścia, ani nie ma dziecka z wyjściem, to w \(v\) musimy już postawić wyjście (aby obsłużyć to dziecko). W przeciwnym wypadku wszystkie dzieci \(v\) są obsłużone i wtedy nie ma potrzeby stawiać wyjścia w \(v\); wystarczy, że wyjście będzie w rodzicu \(v\).

Podzadanie 3 — przypadek ogólny

Łatwo się domyślić, że w ogólnym przypadku także będziemy analizować drzewo w kierunku od liści do korzenia i także będziemy postępować zachłannie. Rozważając jakieś poddrzewo, chcemy postawić w nim jak najmniej wyjść. Jednocześnie wyjścia te chcemy umieścić jak najwyżej (czyli jak najbliżej korzenia drzewa). Intuicyjnie, im wyżej jest wyjście, tym większa szansa, że pomoże nam ono obsłużyć wierzchołki spoza danego poddrzewa. Jednocześnie, umieszczenie wyjść jak wyżej minimalizuje liczbę osób (z wierzchołków położonych blisko korzenia rozważanego poddrzewa), które nie zostaną obsłużone przez żadne wyjście w tym poddrzewie i będą musiały z niego wyjść w górę — do części drzewa, którą dopiero chcemy przetworzyć.

To samo bardziej formalnie

Opiszemy teraz nieco dokładniej powyższe postępowanie zachłanne i uzasadnimy jego poprawność.

Skupmy naszą uwagę na pewnym (dowolnym) poddrzewie naszego drzewa. Niech \(v\) będzie jego korzeniem. Rozwiązaniem dla tego poddrzewa nazwiemy:

wybór wierzchołków tego poddrzewa, które stają się wyjściami ewakuacyjnymi,
kierunki wskazywane przez strzałki w pozostałych jego wierzchołkach (pozwalamy, aby strzałka w wierzchołku \(v\) wskazywała w górę — w kierunku rodzica, znajdującego się już poza rozważanym poddrzewem).

Muszą być przy tym spełnione warunki z zadania: idąc z dowolnego wierzchołka w kierunkach wskazywanych przez strzałki dojdziemy do pewnego wyjścia ewakuacyjnego lub wyjdziemy z rozważanego poddrzewa. Jednocześnie, sumaryczna liczba osób przechodzących jakąkolwiek krawędzią nie może przekroczyć jej przepustowości; dotyczy to także osób wychodzących z naszego poddrzewa krawędzią prowadzącą z \(v\) w górę.

Wynikiem rozwiązania nazwiemy parę liczb \((w,k)\). Liczba \(w\) to po prostu liczba wyjść ewakuacyjnych uwzględnionych w tym rozwiązaniu. Jeśli strzałka w wierzchołku \(v\) wskazuje w górę, to przez \(k\) oznaczymy liczbę osób, które wychodzą tamtędy z poddrzewa. W przeciwnym wypadku \(k\) jest najmniejszą taką liczbą, że jeśli do \(v\) będzie chciało przyjść jeszcze \(-k\) osób z rodzica, to będą oni mogli dojść do wyjścia ewakuacyjnego nie powodując przekroczenia przepustowości żadnej krawędzi, w tym przepustowości krawędzi między \(v\) i jego rodzicem (zatem w tym przypadku \(k\) jest liczbą ujemną, bądź jest to \(0\) jeśli poddrzewo nie jest w stanie przyjąć już żadnych dodatkowych osób). Rozwiązanie nazwiemy optymalnym jeśli ma leksykograficznie najmniejszy wynik wśród wyników wszystkich możliwych rozwiązań dla rozważanego poddrzewa. Wyniki porównujemy leksykograficznie, a więc najpierw liczy się liczba wyjść \(w\), a dla rozwiązań z tą samą liczbą wyjść \(w\) minimalizujemy liczbę \(k\).

Aby powyższe definicje miały sens również dla całego drzewa (a więc gdy \(v\) jest korzeniem drzewa), możemy wyobrazić sobie, że z korzenia jest jeszcze dodatkowa krawędź do wyimaginowanego „nadkorzenia”, o przepustowości \(0\). Wówczas optymalne rozwiązanie dla całego drzewa (a dokładniej liczba \(w\) z jego wyniku) to dokładnie to, czego szukamy w zadaniu.

Poniższy lemat mówi, że podejście zachłanne umożliwia uzyskanie optymalnego rozwiązania.

Lemat. Ustalmy wierzchołek \(v\); niech \(v_1,\dots,v_m\) będą jego dziecmi oraz niech \(R_1,\dots,R_m\) będą ustalonymi rozwiązaniami optymalnymi dla poddrzew zaczynających się w tych dzieciach. Wówczas rozwiązania te można rozszerzyć do rozwiązania optymalnego dla całego poddrzewa zaczynającego się w \(v\).

Dowód. Rozważmy dodatkowo pewne optymalne rozwiązanie \(S\) dla poddrzewa zaczynającego się w \(v\). Niech \(S_1,\dots,S_m\) będą obcięciami tego rozwiązania do poddrzew zaczynających się odpowiednio w \(v_1,\dots,v_m\) (a więc dla wierzchołków należących do takiego poddrzewa bierzemy układ wyjść i strzałek jak w \(S\); daje nam to faktycznie rozwiązanie dla poddrzewa). Oznaczmy przez \((w_i,k_i)\) wynik rozwiązania \(R_i\), a przez \((w'_i,k'_i)\) wynik rozwiązania \(S_i\). Z optymalności rozwiązań \(R_i\) wiemy, że \(w_i\leq w'_i\). Analogicznie, przez \((w,k)\) oznaczymy wynik rozwiązania \(R\) (które za chwilę skonstruujemy), a przez \((w',k')\) wynik rozwiązania \(S\). Mamy dwa przypadki.

Załóżmy najpierw, że dla pewnego \(i\) zachodzi \(w_i < w'_i\). Wówczas \(R\) definiujemy rozszerzając rozwiązania \(R_1,\dots,R_m\) o dodatkowe wyjście w wierzchołku \(v\). Łatwo zobaczyć, że dostajemy w ten sposób poprawne rozwiązanie: w obrębie każdego \(R_i\) każda osoba albo trafia do wyjścia w swoim poddrzewie, albo do \(v\) (gdzie jest wyjście), nie przekraczając przepustowości. Łatwo też zobaczyć, że liczba wyjść \(w\) w \(R\) jest nie większa niż \(w'\): w którymś \(R_i\) mamy co najmniej o jedno wyjście mniej niż w \(S_i\), co równoważy obecność w \(R\) dodatkowego wyjścia w \(v\), które być może nie było obecne w rozwiązaniu \(S\). Ponadto wyjście w \(v\) powoduje, że z rodzica \(v\) może zejść do \(v\) tyle osób, na ile pozwala przepustowość krawędzi między \(v\) i jego rodzicem; zatem liczba \(k\) jest najmniejsza możliwa. To kończy dowód w tym przypadku.
W przeciwnym przypadku mamy \(w_i=w'_i\) dla każdego \(i\). W tej sytuacji \(R\) definiujemy rozszerzając rozwiązania \(R_1,\dots,R_m\) na podstawie \(S\): jeśli w \(S\) było wyjście w \(v\), to budujemy je również w \(R\), a jeśli w \(S\) była strzałka w \(v\), to w \(R\) umieszczamy tam strzałkę w tę samą stronę. Optymalność rozwiązań \(R_i\) mówi nam, że \(k_i\leq k'_i\). Oznacza to, że w \(R\) z wierzchołka \(v_i\) wychodzi do \(v\) nie więcej osób, niż było ich w \(S\) (sytuacja nieujemnych \(k_i,k'_i\)), bądź też w \(R\) do wierzchołka \(v_i\) może zejść z \(v\) nie mniej osób, niż mogło w \(S\) (sytuacja ujemnych \(k_i,k'_i\)), bądź nawet w \(R\) jakieś osoby mogą zejść z \(v\) do \(v_i\) podczas gdy w \(S\) wychodziły z \(v_i\) do \(v\). Tak czy inaczej, teraz (czyli w \(R\)) w wierzchołku \(v\) znajdzie się mniej osób niż przy rozwiązaniu \(S\) i możemy nadal wysłać je w tę samą stronę, co poprzednio. Oznacza, to że \(R\) jest poprawnym rozwiązaniem, a liczba \(k\) jest nie większa niż \(k'\).

To co właściwie robimy?

Jak to co? Jak już powiedzieliśmy, szukamy rozwiązania optymalnego dla coraz to większych poddrzew. Przyjrzyjmy się sytuacji jak w powyższym lemacie: analizujemy wierzchołek \(v\), który ma dzieci \(v_1,\dots,v_m\), a dla poddrzew zaczynających się w tych dzieciach znaleźliśmy już rozwiązania optymalne o wynikach \((w_1,k_1),\dots,(w_m,k_m)\). Niech \(p\) będzie przepustowością krawędzi między \(v\) i jego rodzicem. Ponadto, niech \(s\) będzie sumą dodatnich liczb \(k_i\), plus liczba osób przebywających początkowo w wierzchołku \(v\); jest to więc liczba osób, które znajdą się w \(v\) podczas ewakuacji i muszą się teraz z tego wierzchołka wydostać (nie licząc osób, które potencjalnie mogą jeszcze dojść z rodzica \(v\)). Mamy do wyboru następujące opcje:

Zawsze możemy po prostu postawić wyjście w wierzchołki \(v\). Wówczas wynikiem będzie \((1+w_1+\dots+w_m, -p)\); w szczególności liczba osób, które mogą zejść z góry do \(v\), jest ograniczona jedynie przez przepustowość \(p\)).
Druga opcja to skierowanie wszystkich \(s\) osób z \(v\) w górę, do rodzica \(v\). Jest to możliwe pod warunkiem, że \(p\geq s\), a wynikiem takiego rozwiązania będzie \((w_1+\dots+w_m, s)\).
Trzecia opcja (a dokładniej \(m\) opcji), to skierowanie wszystkich \(s\) osób z \(v\) w dół, do pewnego \(v_i\). Jest to możliwe pod warunkiem, że \(-k_i\geq s\), czyli gdy wierzchołek \(v_i\) jest faktycznie w stanie przyjąć co najmniej \(s\) osób. Może on wówczas przyjąć jeszcze dodatkowe \(-k_i-s\) osób, które mogą przyjść z góry (ale tak czy inaczej z góry nie może przyjść więcej niż \(p\) osób). Wynikiem takiego rozwiązania będzie zatem \((w_1+\dots+w_m,-\min(p,-k_i-s))\).

Możemy więc po prostu rozważyć każdą z tych \(m+2\) opcji (ograniczając się do tych, które są dozwolone) i wybrać tę, która daje najlepszy wynik. Alternatywnie, możemy zobaczyć, że pierwsza opcja zawsze jest najgorsza (ma o \(1\) większą liczbę wyjść), druga opcja jest gorsza od trzeciej (druga współrzędna wyniku jest dodatnia w drugiej opcji, a niedodatnia w trzeciej), a przy trzeciej opcji najlepiej jest wybrać to \(i\) dla którego \(k_i\) jest najmniejsze (czyli powinniśmy kierować ludzi w stronę tego dziecka, które jest w stanie przyjąć ich jak najwięcej).

Powyższe rozważania możemy zupełnie wprost zaimplementować, aplikując je do kolejnych wierzchołków, począwszy od liści i idąc w stronę korzenia. Otrzymujemy program działający w czasie \(O(n)\).