Omówienie zadania Tunele czasoprzestrzenne (eliminacje do IOI 2020, dzień 1)

Wstęp

W zadaniu mamy dany początkowo pusty graf \(G\) oraz aktualizacje postaci dodawania, bądź usuwania z grafu skierowanej krawędzi \(e = uv\), o wadze \(l(e)\). Po każdej z takich aktualizacji chcielibyśmy odpowiedzieć na pytanie, czy w grafie występuje ujemny cykl.

Początkowe podejście

Dla uproszczenia dodajmy do grafu \(G\) wierzchołek \(s\), z którego poprowadzimy skierowane krawędzie o wadze \(0\), do każdego wierzchołka w grafie. Robimy to po to, by graf był spójny; ponadto, nie wpływa to na wynik.
Zastanówmy się, jak najprościej, lecz w rozsądnym czasie dowiedzieć się, czy graf ma ujemny cykl. Zauważmy, że istnieje wtedy podzbiór wierzchołków, dla którego możemy w nieskończoność poprawiać najkrótszą ścieżkę z \(s\).

Możemy więc użyć algorytmu Bellmana-Forda, dzięki któremu jesteśmy w stanie wydobyć odpowiedź w czasie \(O(nm)\) dla jednego zapytania, czyli ostatecznie uzyskując złożoność \(O(nm^2)\).

Drugie podzadanie

Jesteśmy w stanie rozwiązać 1. podzadanie, używając \(O(nm)\) czasu na jedno zapytanie. Możemy więc zastanowić się, czy da się zredukować ilość wywołań Bellmana-Forda, aby zredukować złożoność.
W 2. podzadaniu mamy informację, że do grafu będą jedynie dodawane krawędzie. Zauważmy, że jeżeli w grafie istnieje ujemny cykl, to dodanie krawędzi nie sprawi, że on zniknie.

W takim razie interesuje nas pierwszy moment, w którym taki cykl pojawia się w grafie. Wyszukamy więc binarnie tę aktualizację, która dodaje nam ujemny cykl. Jesteśmy więc w stanie rozwiązać 2. podzadanie w czasie \(O(nm\log m)\).

Co dalej?

Póki co, bazowaliśmy na algorytmie Bellmana-Forda, by odpowiadać na zapytania. Jednak czas \(O(nm)\) to dość dużo na jedno zapytanie, więc musimy pomyśleć nad tym, jak zastąpić ten algorytm.
Naturalnie nasuwa się algorytm Dijkstry, który działa w \(O(m\log n)\). Pamiętajmy jednak, że algorytm ten nie działa, jeżeli mamy do czynienia z ujemnymi krawędziami, więc nie jest on za dobrym pomysłem...

Ale czy na pewno?

Modyfikacja grafu

Fakt, nasz graf zawiera ujemne krawędzie, ale co gdybyśmy poprawili ich wagi w ten sposób, by dało się na nich puścić Dijkstrę, tj. sprawili, że są one nieujemne? Zacznijmy od kilku definicji.

Niech \(\delta_G(u, v)\) oznacza długość najkrótszej ścieżki z \(u\) do \(v\). Przez \(V\) oznaczmy zbiór wszystkich wierzchołków w grafie, a przez \(E\) zbiór wszystkich krawędzi w grafie. Niech \(p: V \to \mathbb{R}\) będzie funkcją potencjału. Niech \(l_p: E \to \mathbb{R}\) będzie zdefiniowane dla \(e = uv\) jako \[ l_p(e) = l(e) + p(u) - p(v). \] Podobnie, niech \(G_p\) będzie grafem \(G\), lecz z wagami zadanymi przez \(l_p\) zamiast \(l\).

Jak skorzystać z powyższej modyfikacji?

Przede wszystkim, zastanówmy się, jak w ogóle definiować \(p\). Pewną funkcję potencjału \(p\) nazwiemy dobrą, gdy \(l_p(e) \geq 0\), dla każdego \(e \in E\).

Zauważmy teraz, że dla dowolnego cyklu \(C\) w \(G\) i potencjału \(p\), koszt przebycia go jest jednakowy względem wag \(l\) oraz \(l_p\). Wysuwa się z tego faktu taki wniosek, że nie jesteśmy w stanie znaleźć takiej funkcji potencjału, która byłaby dobra, podczas gdy w grafie występuje ujemny cykl \((\)warunek \(l_p(e) \geq 0\) byłby złamany dla pewnego \(e \in E)\).

Czy istnieje więc dobra funkcja potencjału, gdy graf nie ma ujemnego cyklu? Owszem, jako funkcję potencjału możemy przyjąć \(p(v) = \delta_G(s, v)\).

W takim razie przekształciliśmy nasze zadanie na zapytania o to, czy istnieje dobra funkcja potencjału dla zadanego grafu, tj. czy zdefiniowane jest \(\delta_G(s, v)\) dla każdego wierzchołka \(v \in V\).

Trzecie podzadanie

Będziemy utrzymywać dobrą funkcję potencjału \(p\). Zauważmy, że jeśli \(p\) jest dobrą funkcją potencjału, to usunięcie krawędzi tego nie zmieni.

Załóżmy teraz, że dodajemy do grafu krawędź \(e = uv\). Ujemny cykl powstanie wtedy, gdy \[ \delta_G(v, u) + l(e) < 0. \] Z faktu, że koszt przejścia po cyklu \(C\) jest taki sam zarówno w \(G\), jak i w \(G_p\), to ujemny cykl powstanie również wtedy, gdy \[ \delta_{G_p}(v, u) + l_p(e) < 0. \] Wiemy, że \(p\) jest dobrą funkcją potencjału, więc \(\delta_{G_p}(v, u)\) wyznaczamy, puszczając algorytm Dijkstry z \(v\) do \(u\) po \(G_p\), w którym wagi na krawędziach są nieujemne.

Jeśli okaże się, że utworzyliśmy ujemny cykl, to w następnym zapytaniu usuniemy krawędź \(e\) i wrócimy do stanu sprzed aktualizacji. Jeśli zaś okaże się, że nie mamy ujemnego cyklu, to trzeba od nowa przeliczyć potencjał, puszczając algorytm Dijkstry z \(s\).

Dlaczego możemy użyć algorytmu Dijkstry do poprawy potencjału? Faktem jest, że: \[ \delta_{G+e}(s, x) = \min\left(\delta_{G}(s, x), \delta_{G}(s, u) + \ell(e) + \delta_{G}(v, x)\right), \] co jest równoważne: \[ \delta_{G+e}(s, x) = \min\left(\delta_{G_p}(s, x), \delta_{G_p}(s, u) + \ell_p(e) + \delta_{G_p}(v, x)\right) - p(s) + p(x). \] Oznacza to, że możemy przeprowadzić algorytm Dijkstry bezpośrednio na \(G_p\), który nie zawiera ujemnych krawędzi. Tak więc dla każdego zapytania puszczamy dwa razy algorytm Dijkstry, co daje nam złożoność \(O(m^2 \log n)\).

Rozwiązanie wzorcowe

W poprzednim podzadaniu nie musieliśmy operować na grafie, który zawiera ujemne cykle. Niestety, potencjał nie jest zdefiniowany dla grafu z ujemnym cyklem, ponieważ istnieje taki wierzchołek \(v \in V\), dla którego niedefiniowane jest \(\delta_G(s, v)\).

Chcielibyśmy dowolny przypadek sprowadzić do poprzedniego podzadania. Zrobimy to, w każdym momencie trzymając podgraf, który nie ma ujemnego cyklu, oraz jego potencjał.

Dokładniej, podzielmy zbiór krawędzi na trzy rozłączne zbiory takie, że \(E = E_0 \cup \{e^*\} \cup E_1\). Przy czym, jeżeli \(G\) nie ma ujemnego cyklu, to \(E_0 = E\).
W przeciwnym przypadku:

• \(G_0 = (V, E_0)\), nie ma ujemnego cyklu,
• \(G_0^* = (V, E_0 \cup \{e^*\})\), ma ujemny cykl.

Zauważmy, że z definicji \(G_0\), każdy ujemny cykl przechodzi przez \(e^*\).

Dopóki \(G\) nie ma ujemnego cyklu, postępujemy jak w poprzednim podzadaniu. Załóżmy, że dodajemy pewną krawędź \(e\) i powstaje ujemny cykl. Wtedy ustawiamy \(G_0 := (V, E)\), \(e^* := e\), \(E_1 = \emptyset\).

Załóżmy teraz, że \(G\) ma już ujemny cykl i następuje kolejna aktualizacja. Jeżeli \(e\) jest dodawana, to jest to proste: dodajemy ją do \(E_1\).
Pochylmy się więc nad przypadkiem, w którym \(e\) jest usuwane z \(G\).
Mamy dwa przypadki:

• Jeżeli \(e \in E_1\), to zmiana ta nie usunie wszystkich ujemnych cykli z \(G\), więc po prostu usuwamy tę krawędź z \(E_1\).
• W przeciwnym razie \(e \in E_0 \cup \{e^*\}\). Jeżeli \(e = e^*\), to w oczywisty sposób \(G_0^* - e\) nie ma ujemnych cykli. Zaraz zajmiemy się tym przypadkiem. Jeśli \(e \neq e^*\), to jak w poprzednim podzadaniu sprawdzamy, czy \(G_0^* - e\) ma ujemny cykl, weryfikując warunek: \[ \delta_{G_0-e}(y, x) + \ell(e^*) = \delta_{(G_0-e)_p}(y, x) + \ell_p(e^*) < 0, \] gdzie \(e^* = xy\). Możemy to sprawdzić, używając algorytmu Dijkstry.
  Jeżeli \(G_0^* - e\) nadal ma ujemny cykl, usuwamy \(e\) z \(E_0\) i wszystko się zgadza.
  Jeżeli jednak \(G_0^* - e\) nie ma już ujemnych cykli, to wykonujemy następujące kroki:
  • Ustawiamy \(E_0 := E_0 \cup \{e^*\} \setminus \{e\}\).
  • Usuwamy po jednej krawędzi \(e' \in E_1\), sprawdzając (Dijkstrą), czy \(G_0 + e'\) ma ujemny cykl.
  • Jeżeli \(G_0 + e'\) nie ma ujemnego cyklu, dodajemy \(e'\) do \(E_0\).
  • W przeciwnym przypadku ustawiamy \(e^* := e'\) i stwierdzamy, że graf nadal ma ujemny cykl.

Zauważmy, że każda krawędź zostanie przełożona z \(E_1\) co najwyżej raz, więc algorytm Dijkstry zostanie wywołany dla każdej krawędzi co najwyżej dwa razy. Sumaryczna złożoność czasowa naszego algorytmu wynosi zatem \(O(m^2 \log m)\).