Omówienie zadania Metro (III etap XXVI OI)

W zadaniu tym mamy do czynienia ze spójną siecią drogową składającą się z \(n\) skrzyżowań i \(n - 1\) kierunkowych dróg. Wobec tego nie będzie zaskoczeniem, że sieć tę zamodelujemy jako graf będący drzewem. Burmistrz chce wybudować w mieście metro, jego stacje staną przy niektórych skrzyżowaniach, a tunele zostaną poprowadzone pod niektórymi drogami, przy czym całość również musi być spójna.

Tak więc, przekładając to na język teorii grafów, chcemy w naszym drzewie wybrać pewien podgraf, który również będzie drzewem. Na to drzewo zostało nałożone pewne ograniczenie: wierzchołków, do których prowadzi tylko jedna krawędź w tym drzewie (czyli liści tego drzewa) może być co najwyżej \(k\).

Naszym zadaniem będzie zaplanowanie sieci metra spełniającej powyższe ograniczenia, ale jednocześnie jak najbardziej przyjaznej pasażerom. W tym celu będziemy chcieli wybrać takie poddrzewo, które minimalizuje maksymalną odległość od dowolnego wierzchołka oryginalnego drzewa do pewnego wierzchołka naszego poddrzewa (tzw. współczynnik irytacji).

Rozwiązanie wzorcowe

Zacznijmy od odpowiedzi na pytanie, kiedy możemy uzyskać minimalny możliwy współczynnik irytacji dla poddrzewa, równy oczywiście \(0\). Jest tak tylko wtedy, kiedy jako nasze poddrzewo wybierzemy całe drzewo.

Wobec tego z ograniczeń wynika nam, że liczba liści w całym drzewie musi być co najwyżej równa \(k\). Jeżeli to nie jest prawdą, to wtedy współczynnik irytacji będzie musiał być równy co najmniej \(1\), a my będziemy musieli zmniejszyć nasze wybrane poddrzewo. Ponieważ to wybrane poddrzewo musi być spójne, więc możemy je zmniejszać, zaczynając właśnie od liści.

Zauważmy, że liście możemy spokojnie usuwać z naszego poddrzewa, bez martwienia się o współczynnik irytacji: jeżeli usuniemy tylko liść, to odległość od tego usuniętego liścia do jego nieusuniętego rodzica będzie właśnie równa \(1\), czyli będzie umieścić się w aktualnie rozpatrywanym współczynniku irytacji.

Zauważmy jeszcze jedną ważną własność. Gdy usuwamy liść z naszego poddrzewa, to całkowita liczba liści w poddrzewie nigdy nie może wzrosnąć. Może albo zmaleć o \(1\) (wtedy, kiedy usuwamy liść podpięty pod wierzchołek o stopniu równym co najmniej \(3\)), albo pozostać taka sama (wtedy, kiedy usuwamy liść podpięty pod wierzchołek o stopniu \(2\) – po usunięciu liścia ten właśnie wierzchołek staje się nowym liściem).

Tak więc, aby stworzyć poddrzewo o współczynniku irytacji równym \(1\), zawierające minimalną liczbę liści, możemy usunąć wszystkie liście z oryginalnego drzewa. Część wierzchołków, do których te liście były podpięte, staną się liśćmi naszego nowego poddrzewa.

Nietrudno się teraz przekonać, że aby stworzyć minimalne drzewo dla współczynnika irytacji równego \(2\), możemy usunąć wszystkie liście w zbudowanym minimalnym poddrzewie dla współczynnika irytacji równego \(1\). Taką procedurę możemy powtarzać dla większych współczynników irytacji.

Implementacja

Możemy ten pomysł zaimplementować następująco. Na początek dla każdego wierzchołka obliczamy jego stopień, czyli liczbę wierzchołków, z którymi jest połączony. Następnie w kolejnych fazach będziemy usuwali z grafu wszystkie wierzchołki o stopniu \(1\) i będziemy dla każdego wierzchołka zapisywać, w której fazie został on usunięty. Czyli w fazie \(0\) zaznaczymy to dla liści oryginalnego drzewa (czyli wierzchołków o stopniu \(1\)), a następnie usuniemy je z drzewa, zmniejszając stopnie wszystkich ich sąsiadów.

To spowoduje, że w fazie \(1\) zaznaczymy nowe wierzchołki o stopniu \(1\) i znowu usuniemy je z grafu, zmniejszając stopnie ich sąsiadów, ale tylko tych, których jeszcze z grafu nie usunęliśmy. Podobnie dla kolejnych faz, aż usuniemy wszystkie wierzchołki z grafu.

Nietrudno jest zaimplementować całą tę operację w czasie liniowym od wielkości drzewa. Pewien kłopot może tu jedynie sprawiać fakt, że musimy operować na drzewie nieukorzenionym, ale jeżeli chcemy, możemy ten algorytm również zapisać w wersji ukorzenionej.

Gdybyśmy bowiem ukorzenili nasze drzewo w wierzchołku z ostatniej fazy, to wtedy numer fazy obliczonej dla każdego wierzchołka to byłaby odległość od tego wierzchołka w dół skierowanego drzewa do najdalszego liścia. A takie coś jesteśmy w stanie policzyć w czasie liniowym, prostym programowaniem dynamicznym. Jednak w tym rozwiązaniu trudność polega na odpowiednim wyborze korzenia, gdy nie mamy jeszcze policzonych faz dla wierzchołków. Okazuje się jednak, że jako korzeń możemy wybrać środkowy wierzchołek dowolnej średnicy naszego drzewa, czyli dowolnej najdłuższej ścieżki w drzewie. A znalezienie takowej średnicy również jest standardowym problemem.

Ostatecznie, gdy mamy już policzone fazy dla wszystkich wierzchołków, wybieramy sobie taki minimalny numer fazy, że liczba wierzchołków z tej fazy jest mniejsza lub równa od \(k\) i wypisujemy te właśnie wierzchołki, a numer fazy to będzie znaleziony minimalny współczynnik irytacji. Należy jeszcze uważać na przypadek szczególny. Jeżeli z naszego algorytmu wynikałoby, że optymalnie jest wypisać jeden wierzchołek, to musimy do tego wierzchołka dodać dowolny inny, po to, żeby zadośćuczynić wymaganiu z treści zadania, że minimalna liczba stacji metra musi być równa \(2\).