Omówienie zadania Wykaz dróg (II etap XXXIII OI)

Formalna treść zadania

Dany mamy graf skierowany o \(n \) wierzchołkach (\(n \leq 1500\)) i \(m\) krawędziach (\(0 \leq m \leq n(n-1)\)). Można dodawać krawędzie do grafu jedynie pomiędzy wierzchołkami \(a\) i \(b\), pomiędzy którymi w momencie dodawania tej krawędzi nie istnieje skierowana ścieżka z \(a\) do \(b\).

Należy znaleźć optymalną kolejność dodawania krawędzi, tak aby liczba dodanych krawędzi była jak największa.

Pierwsze podzadanie – \(n \le 5\)

W tym podzadaniu limity pozwalają na sprawdzenie wszystkich możliwości kolejności dodawania krawędzi. Graf możemy reprezentować za pomocą macierzy osiągalności, w której \(a_{ij} = 1\) oznacza istnienie ścieżki z wierzchołka \(i\) do wierzchołka \(j\), a \(a_{ij} = 0\) oznacza brak takiej ścieżki. Początkowo wypełniamy macierz na podstawie danych wejściowych.

Następnie przetwarzamy wszystkie możliwe stany zbioru krawędzi, jednocześnie pamiętając krawędzie, których dodanie doprowadziło nas do tego stanu. W każdej iteracji dla ustalonego stanu próbujemy dodać nieistniejące krawędzie oraz aktualizujemy macierz osiągalności. Ponieważ \(n \le 5\), liczba możliwych krawędzi jest ograniczona przez \(20\), co umożliwia sprawdzenie wszystkich podzbiorów tych krawędzi.

Złożoność czasowa: \(O(2^{n(n-1)} \cdot n^3)\) ze względu na iterację po wszystkich możliwych podzbiorach krawędzi oraz konieczność aktualizacji macierzy osiągalności w czasie \(O(n^3)\) (przykładowo za pomocą algorytmu Floyd-Warshalla lub przeszukiwaniu grafu rozpoczynając z każdego wierzchołka).

Drugie podzadanie – \(m = 0\) oraz \(n \le 500\)

Zastanówmy się, jak może wyglądać optymalna konstrukcja dla grafu bez krawędzi. Okazuje się, że maksymalna liczba dodanych krawędzi jest równa \[\frac{(n+2)(n-1)}{2}.\]

Możemy taką konstrukcję zrealizować poprzez dodawanie krawędzi w następujący sposób: najpierw dodajemy krawędzie z wierzchołka \(1\) do wszystkich pozostałych wierzchołków, następnie z wierzchołka \(2\) do wszystkich wierzchołków o numerach większych, i tak dalej. Formalnie, dla każdego wierzchołka \(i\) (od \(1\) do \(n-1\)) dodajemy krawędzie do wszystkich wierzchołków \(j\) (o numerach od \(i+1\) do \(n\)).

Gdyby w momencie dodawania krawędzi z \(i\) do \(j\) ścieżka między tymi wierzchołkami już istniała, to musi się składać z przynajmniej dwóch krawędzi (bo bezpośredniej krawędzi jeszcze nie dodaliśmy). Niech \(i < k < j\) będzie drugim wierzchołkiem na ścieżce z \(i\) do \(j\). Ale wierzcholek \(k\) ma stopień wyjściowy równy \(0\), stąd taka ścieżka nie może istnieć. Zatem taka konstrukcja jest poprawna. W ten sposób dodajemy \(\sum_{i=1}^{n-1} (n - i) = \frac{n(n-1)}{2}\) krawędzi.

W tym momencie w grafie istnieją krawędzie (i ścieżki) od wierzchołka \(i\) do wierzchołka \(j\) wtedy i tylko wtedy gdy \(i < j\) i już nie da się dodać krawędzi z wierzchołków o mniejszych numerach do wierzchołków o większych numerach. Możemy zatem jeszcze dodać krawędzie w odwrotnym kierunku – od wierzchołka \(i+1\) do wierzchołka \(i\), dla wszystkich \(i\) od \(n-1\) do \(1\). W ten sposób dodajemy jeszcze \((n-1)\) krawędzi. Łącznie mamy \(\frac{(n-1)n}{2} + (n-1) = \frac{(n+2)(n-1)}{2}\) krawędzi.

Dlaczego to jest optymalna konstrukcja?

Niech \(f_n\) będzie liczbą dodanych krawędzi w optymalnym rozwiązaniu dla początkowo pustego grafu o \(n\) wierzchołkach. Dla \(n = 1\) mamy \(f_1 = 0\), ponieważ nie można dodać żadnej krawędzi. Zauważmy, że na koniec procesu w naszym grafie będzie dokładnie jedna silnie spójna składowa (w przeciwnym przypadku istnieje para wierzchołków, między którymi jeszcze nie istnieje skierowana ścieżka i możemy polepszyć nasz wynik). Zastanówmy się, jak może wyglądać krawędź \(e\) dodana jako ostatnia. Niech będzie to krawędź z wierzchołka \(a\) do wierzchołka \(b\). Tuż przed dodaniem krawędzi \(e\) w grafie muszą być dokładnie dwie silnie spójne składowe (bo gdyby ich było więcej, to również możemy polepszyć nasz wynik). W jednej z tych spójnych składowych musi być wierzchołek \(a\), a w drugiej wierzchołek \(b\), bo gdyby \(a\) i \(b\) były w tej samej spójnej składowej, to istniałaby już ścieżka z \(a\) do \(b\) i nie moglibyśmy dodać krawędzi \(e\).

Niech rozmiary tych spójnych składowych zawierających \(a\) i \(b\) to odpowiednio \(A\) i \(B\). Krawędzi z silnie spójnej składowej rozmiaru \(B\) do silnie spójnej składowej rozmiaru \(A\) może być co najwyżej \(A \cdot B\). Zauważmy, że możemy dodać te krawędzie na samym początku procesu i nie zmieni to poprawności naszej konstrukcji. Następnie, silnie spójne składowe rozmiaru \(A\) i \(B\) mają maksymalnie \(f_A\) i \(f_B\) krawędzi, odpowiednio. Po dodaniu krawędzi \(e\) otrzymujemy graf o \(n\) wierzchołkach, który ma co najwyżej \(A \cdot B + f_A + f_B + 1\) krawędzi. Zauważmy, że \(A + B = n\), więc \[A \cdot B + f_A + f_B + 1 = A \cdot B + \frac{(A+2)(A-1)}{2} + \frac{(B+2)(B-1)}{2} + 1 = \frac{(n+2)(n-1)}{2}.\] Oznacza to, że nasza konstrukcja jest optymalna.

Podzadanie trzecie – \(a_i < b_i\) dla wszystkich \(1 \leq i \leq m\) oraz \(n \le 500\)

W tym podzadaniu dany mamy graf skierowany acykliczny. Obliczmy na samym początku w złożoności \(O(n^3)\) macierz osiągalności (na przykład z wykorzystaniem Floyd-Warshalla). Niech \(m'\) będzie liczbą par ścieżek \((a, b)\) takich, że \(a < b\) i istnieje ścieżka z \(a\) do \(b\) w wejściowym grafie. Wówczas maksymalna liczba krawędzi, które możemy dodać, jest ograniczona z góry przez \(f_n - m'\). Pokażemy, że to ograniczenie górne jest osiągalne.

Przykładowa działająca konstrukcja działa w podobny sposób, co konstrukcja rozpoczynająca z pustym grafem (uważny czytelnik zauważy, że poniższe fazy są niczym innym, jak algorytmem z podzadania drugiego, z transponowanymi krawędziami). Będzie \(n-1\) faz dodawania krawędzi (numerowane od \(1\) do \(n-1\)). W trakcie \(i-\)tej fazy dodajemy krawędzie z wierzchołków o numerach \(j\) spełniających \(j \le n - i\) do wierzchołka \((n-i+1)\), przy czym w momencie do dodawania krawędzi nie może istnieć ścieżka z \(j\) do \((n-i+1)\) w wejściowym grafie. Numery \(j\) rozpatrujemy rosnąco. Kolejność dodawania krawędzi gwarantuje nam, że dodawane przez nas krawędzie nie będą zmieniać osiągalności wszystkich pozostałych par wierzchołków. Następnie analogicznie, jak w podzadaniu drugim, łączymy \(n\) jednoelementowych spójnych składowych w jedną spójną składową.

Rozwiązanie ma złożoność czasową \(O(n^3)\) ze względu na konieczność obliczenia macierzy osiągalności.

Podzadanie piąte – \(n \le 500\)

Teraz mamy do czynienia z ogólnym przypadkiem, w którym graf może zawierać cykle. Wówczas na pewno w obrębie jednej silnie spójnej składowej nie będziemy w stanie dodać żadnej krawędzi bez naruszania warunków zadania. Za pomocą algorytmu Tarjana możemy zatem znaleźć silnie spójne składowe w czasie \(O(n+m)\). Następnie, rozpatrując silnie spójne składowe skondensowane do jednego wierzchołka (wystarczy, że wybierzemy dowolny wierzchołek z danej silnie spójnej składowej jako jego reprezentanta), otrzymujemy graf skierowany acykliczny, dla którego możemy zastosować rozwiązanie z podzadania trzeciego. Ostateczna złożoność czasowa rozwiązania to \(O(n^3)\) ze względu na konieczność obliczenia macierzy osiągalności dla skondensowanego grafu. Z kolei złożoność pamięciowa to \(O(n^2)\) ze względu na przechowywanie macierzy osiągalności.

Pełne rozwiązanie – \(n \le 1500\)

Aby jeszcze bardziej przyspieszyć rozwiązanie poprzedniego podzadania, zauważmy, że wyliczanie macierzy osiągalności przy użyciu Floyd-Warshalla możemy przyspieszyć za pomocą struktury \(\texttt{std::bitset}\). W ten sposób złożoność czasowa rozwiązania to \(O(n^3 / 64)\), co pozwala na otrzymanie pełnej liczby punktów.