Wojciech GuzickiAndrzej Gąsienica--Samek
Treść zadania, OpracowanieProgram wzorcowy


Wyspa


Na wyspie o kształcie wielokąta wypukłego o 2n bokach, znajduje się 2n-2 państw - trójkątów, których wierzchołki są jednocześnie wierzchołkami wielokąta. Nie ma państw graniczących dokładnie z dwoma innymi państwami (zatem każde państwo graniczy albo tylko z jednym państwem, albo z trzema).

Wynika stąd, że istnieje dokładnie n państw graniczących tylko z jednym państwem (są to państwa nadmorskie) oraz n-2 państw graniczących z trzema sąsiadami (są to państwa wewnątrzlądowe). Państwa nadmorskie są ponumerowane liczbami od 1 do n, natomiast państwa wewnątrzlądowe mają numery od n+1 do 2n-2.

Gdy podróżujemy z jednego państwa do drugiego, to za przekroczenie każdej granicy musimy zapłacić ustaloną stawkę. Poszczególne stawki mogą być różne, ale przekroczenie granicy w obu kierunkach kosztuje tyle samo.


Dla każdych dwóch państw, spośród n państw nadmorskich, znana jest suma opłat granicznych na drodze prowadzącej (lądem) od jednego państwa do drugiego przez najmniejszą liczbę granic. Zadanie polega na wyznaczeniu wszystkich opłat granicznych na całej wyspie. Dla każdego państwa nadmorskiego należy podać numer państwa, z którym ono graniczy, oraz wysokość odpowiedniej opłaty granicznej. Ponadto, dla każdego z n-2 państw wewnątrzlądowych należy podać numery trzech państw, z którymi ono graniczy, oraz wysokości opłat na granicach z tymi państwami.

Zadanie

Napisz program, który:

Wejście

W pierwszym wierszu pliku tekstowego wys.in znajduje się jedna dodatnia liczba całkowita n, 4 leq n leq 100. Jest to liczba państw nadmorskich. W każdym z następnych n wierszy znajduje się n nieujemnych liczb całkowitych oddzielonych pojedynczymi odstępami. Liczba d_(i,j), stojąca na j-tym miejscu w i-tym z tych wierszy, jest równa sumie opłat granicznych na drodze prowadzącej (lądem, przez najmniejszą liczbę granic) z państwa o numerze i do państwa o numerze j. Zakładamy przy tym, że na każdej granicy opłata graniczna jest liczbą całkowitą z przedziału [1... 100]. Oczywiście, d_(i,j)=d_(j,i) oraz d_(i,i)=0.

Wyjście

W pierwszych n wierszach pliku tekstowego wys.out należy zapisać po dwie liczby całkowite oddzielone pojedynczym ostępem. Pierwszą liczbą w i-tym wierszu powinien być numer państwa graniczącego z państwem o numerze i, a drugą wysokość opłaty granicznej na granicy między tymi dwoma państwami. W każdym z następnych n-2 wierszy należy zapisać po sześć liczb oddzielonych pojedynczymi odstępami. W wierszu o numerze i (licząc od początku pliku, a więc i>n) pierwszą liczbą ma być numer pierwszego państwa graniczącego z państwem o numerze i, drugą ma być wysokość opłaty granicznej na tej granicy, trzecią ma być numer drugiego państwa graniczącego z państwem o numerze i, czwartą wysokość opłaty granicznej na drugiej granicy, piątą ma być numer trzeciego państwa graniczącego z państwem o numerze i, szóstą ma być wysokość opłaty granicznej na trzeciej granicy. Państwa wewnątrzlądowe mogą być ponumerowane dowolnie liczbami od n+1 do 2n-2.

Przykład

Dla pliku przykładowego wys.in:

7
0 8 10 8 13 11 14
8 0 8 10 11 5 12
10 8 0 12 5 11 6
8 10 12 0 15 13 16
13 11 5 15 0 14 3
11 5 11 13 14 0 15
14 12 6 16 3 15 0

poprawną odpowiedzią jest plik wyjściowy wys.out (zobacz też rysunek obok):

12 3
10 1
9 1
12 5
8 1
10 4
8 2
5 1 7 2 9 3
3 1 8 3 11 4
2 1 6 4 11 2
9 4 10 2 12 2
1 3 4 5 11 2

        

epsffile(wyszad.1)

Rozwiązanie

Będziemy używać terminologii teorii grafów - ułatwi to zaprezentowanie możliwych algorytmów prowadzących do rozwiązania zadania. Najprościej mówiąc, grafem nazywamy skończony zbiór punktów na płaszczyźnie (te punkty będziemy zaznaczać na rysunku ,,grubymi'' kropkami) oraz pewien zbiór odcinków łączących te punkty. Wybrane punkty nazywamy wierzchołkami grafu, wybrane odcinki krawędziami grafu. Te krawędzie mogą się przecinać, będziemy tylko zakładać, że punkt przecięcia dwóch krawędzi nie może być wierzchołkiem grafu. Wierzchołki grafu będziemy numerować początkowymi liczbami naturalnymi, zaczynając od 1.

Krawędziom grafu będziemy przyporządkowywać pewne liczby rzeczywiste. Liczbę rzeczywistą przyporządkowaną krawędzi łączącej wierzchołki k i l będziemy nazywać długością tej krawędzi i będziemy oznaczać symbolem d_(k,l).

Liczbę krawędzi wychodzących z jednego wierzchołka nazywamy stopniem tego wierzchołka.

W naszym przypadku wierzchołki grafu będą odpowiadać państwom na wyspie. Dwa wierzchołki łączymy krawędzią, jeśli odpowiadające im państwa graniczą ze sobą. Wreszcie długością krawędzi będzie koszt przekraczania granicy. Zauważmy, że w naszym grafie stopień każdego wierzchołka jest równy 1 (dla państw nadmorskich) lub 3 (dla państw wewnątrzlądowych). Nasz graf ma jeszcze jedną ważną własność wynikającą z geometrii wyspy: nie ma w nim cykli. To znaczy, że nie można wyjść z jednego wierzchołka, poruszać się po krawędziach przez inne wierzchołki i powrócić do punktu wyjścia nie przechodząc przez żaden z wierzchołków więcej niż raz. Ponadto z każdego wierzchołka można dojść do każdego innego. Takie grafy nazywamy drzewami. Jedną z ważnych własności drzew, wynikającą wprost z tego, że w drzewie nie ma cykli, jest to, że każde dwa wierzchołki łączy tylko jedna droga przebiegająca wzdłuż krawędzi. Długość tej jedynej drogi łączącej wierzchołki k i l (równa sumie długości krawędzi, przez które ta droga przebiega) oznaczymy również symbolem d_(k,l). Jeśli dwa wierzchołki są połączone krawędzią, to oczywiście drogą łączącą je jest ta krawędź, a więc długość tej drogi jest równa długości krawędzi. Zatem użycie tego samego oznaczenia na długość krawędzi i długość drogi nie będzie prowadzić do nieporozumień.

Popatrzmy teraz na przykład. Drzewo odpowiadające wyspie z treści zadania ma postać:

epsffile(wys01.eps)

Wierzchołki stopnia 1 nazywamy liśćmi drzewa. Pozostałe wierzchołki będziemy nazywać węzłami.

Danymi dla zadania są długości dróg łączących liście drzewa. Zadanie polega na tym, by odtworzyć drzewo mając dane wyłącznie odległości między liśćmi. Jest to możliwe dzięki założeniu, że wszystkie węzły mają stopień równy 3. Najprostszy algorytm odtwarzania drzewa polega na znajdowaniu dwóch sąsiednich liści (dwa liście nazywamy sąsiednimi, gdy sąsiadują z tym samym węzłem) i zastępowaniu ich węzłem, z którym sąsiadują. Przypuśćmy, że liście o numerach i oraz j sąsiadują z węzłem o numerze k. Usuwamy z tablicy kosztów wiersze i kolumny o numerach i oraz j i dopisujemy nowy wiersz i nową kolumnę o numerze k. W jaki sposób obliczamy długość drogi z węzła k do dowolnego innego liścia m? Zauważmy, że

 d_(i,m)+d_(j,m)=2cd...
Stąd otrzymujemy wzór
 d_(k,m)=(1 over 2)c...
Oczywiście długości krawędzi (i,k) i (j,k) obliczamy natychmiast ze wzorów
 d_(i,k)=d_(i,m)-d_(...
oraz
 d_(j,k)=d_(j,m)-d_(...
Tak więc, gdy usuwamy dwa liście, tworzymy nowy liść o kolejnym numerze, znajdujemy odległości od tego nowego liścia do pozostałych liści i obliczamy długości usuniętych krawędzi. Wszystkie te dane zapisujemy w odpowiednich tabelach; wypiszemy je po zakończeniu algorytmu. Popatrzmy teraz na tabelę długości dróg.

centerline(
vbox(tab...

Weźmy sąsiednie liście o numerach 5 i 7. Usuwając je z drzewa otrzymujemy drzewo mniejsze, w którym mamy nowy liść o numerze 8:

epsffile(wys02.eps)

Obliczając długości dróg z liścia 8 do pozostałych liści według powyższego wzoru, otrzymamy następującą tabelę długości dróg między liśćmi nowego drzewa:

centerline(
vbox(tab...

Teraz znajdujemy następne dwa sąsiednie liście: na przykład 3 i 8. Usuwamy je z drzewa i do tablicy długości dróg dopisujemy nowy liść o numerze 9. Nowe drzewo ma postać:

epsffile(wys03.eps)

a odpowiednia tabela długości dróg między liśćmi tego drzewa ma postać:

centerline(
vbox(tab...

Kontynuujemy to postępowanie. Znajdujemy kolejne sąsiednie liście: 2 i 6. Usuwamy je z drzewa i z tablicy długości dróg, dopisując nowy liść o numerze 10. Otrzymamy następne drzewo i odpowiadającą mu tablicę długości dróg:

epsffile(wys04.eps)

centerline(
vbox(tab...

Jeszcze raz usuwamy dwa sąsiednie liście: tym razem o numerach 9 i 10. Dopisujemy nowy liść o numerze 11. Otrzymamy nowe drzewo i odpowiadającą mu tablicę długości dróg:

epsffile(wys05.eps)

centerline(
vbox(tab...

Mamy teraz drzewo z trzema liśćmi. Ma ono tylko jeden wierzchołek stopnia 3: dajmy mu numer 12. Oczywiście teraz mamy

 displaylines(
d_(1,...

W ten sposób całe drzewo zostało odtworzone. Jedynym istotnym problemem w tym algorytmie jest to, w jaki sposób znajdować dwa sąsiednie liście. W powyższym przykładzie za każdym razem wybieraliśmy dwa liście położone najbliżej siebie (tzn. liście i oraz j, dla których liczba d_(i,j) jest najmniejsza). To udało się tylko dlatego, że drzewo z przykładu zostało specjalnie dobrane! Ten sposób wybierania sąsiednich liści na ogół jest niepoprawny. Popatrzmy na inny przykład drzewa i odpowiadającej mu tabeli odległości:

epsffile(wys06.eps)

centerline(
vbox(tab...

Zauważmy, że najbliżej położone liście (o numerach 1 i 2) nie są sąsiednie! Gdybyśmy mimo to próbowali zastosować poprzedni algorytm do tej sytuacji, otrzymalibyśmy kolejno następujące tabele odległości:

centerline(
vbox(tab...

centerline(
vbox(tab...

Teraz poprzednie wzory dadzą nam następujące długości krawędzi łączących liście 4, 5 i 7 z wierzchołkiem 8:

 d_(4,8)=9, quad d_(...
Algorytm zakończył się niepowodzeniem, gdyż długość krawędzi nie może być liczbą ujemną.

Istnieją dwie metody znajdowania sąsiednich liści. Jedna z nich polega na obliczeniu dla każdego liścia i wielkości

 r_i = sum_(j)(d_(i,...
gdzie sumowanie jest rozciągnięte na wszystkie liście. Następnie dla każdej pary liści i oraz j obliczamy
 D_(i,j)=d_(i,j)-(r_...
Można wtedy udowodnić twierdzenie mówiące, że liście i oraz j, dla których wartość D_(i,j) jest najmniejsza, są sąsiednie.

Twierdzenie to jest dość sztuczne i nieoczekiwane. Potrzebny jest sposób prostszy i bardziej naturalny. Wybieramy dowolny liść, na przykład o najmniejszym numerze. Niech będzie to numer k. Szukamy liścia sąsiadującego z liściem o numerze l. W tym celu dla każdego liścia m wyznaczamy długość wspólnego odcinka dróg z k do l i z k do m. Jeśli te drogi rozchodzą się w węźle p, to

 d_(k,p)=(1 over 2)c...
Możliwe są teraz dwa przypadki. Jeśli liście k i l sąsiadują ze sobą, to węzeł p wypada zawsze w tym samym miejscu i to można łatwo stwierdzić. Jeśli liście k i l nie sąsiadują ze sobą, to znaleziona długość d_(k,p) jest największa wtedy, gdy liść m sąsiaduje z liściem l. W obu przypadkach znajdujemy parę liści sąsiednich: najczęściej będzie to liść l i pewien liść m, może się też zdarzyć, że będą to liście k i l. Poszukiwanie takiej pary liści sąsiednich wymaga czasu O(n), zatem cały algorytm działa w czasie O(n2).

Inny algorytm polega na sukcesywnym budowaniu drzewa. Zaczynamy od drzewa złożonego tylko z liści o numerach 1 i 2 i krawędzi łączącej te liście. Ma ona długość d_(1,2). W naszym przykładzie to drzewo ma postać:

epsffile(wys07.eps)

Teraz dołączamy następny liść. Na drodze z liścia 1 do liścia 2 znajduje się węzeł (nadamy mu numer 8), w którym odgałęzia się droga do liścia 3. Można łatwo wyznaczyć długość odcinka od liścia 3 do węzła 8:

 d_(1,3)+d_(2,3)=2 c...
Stąd dostajemy d_(8,3)=5 i następnie
 d_(1,8)=d_(1,3)-d_(...
Możemy teraz narysować drzewo:

epsffile(wys08.eps)

Teraz dołączamy kolejny liść, o numerze 4, wraz z węzłem sąsiadującym z nim. Mamy trzy możliwości. Droga prowadząca z liścia 4 do któregokolwiek z pozostałych liści musi ,,dołączyć'' się do jednej z dróg: z liścia 1 do węzła 8, z liścia 2 do węzła 8 lub z liścia 3 do węzła 8. Oznaczmy liście i węzły literami: węzeł 8 oznaczmy literą m, liść 4 oznaczmy literą l, literą k oznaczmy ten z liści 1,2 lub 3, dla którego droga z k do l nie przechodzi przez m. Pozostałe dwa liście oznaczymy literami i oraz j. Wreszcie literą p oznaczymy węzeł na drodze z k do m, w którym odgałęzia się droga do l. Tę sytuację możemy przedstawić na rysunku:

epsffile(wys09.eps)

Na rysunku grubszą linią zaznaczono krawędzie drzewa przed dołączeniem liścia l i węzła p, cieńszymi liniami zaznaczono krawędzie drzewa po dołączeniu tych nowych wierzchołków. Zauważmy, że musi być spełniona nierówność

 d_(i,k)+d_(j,l) > d...
Sprawdzamy zatem tę nierówność dla trzech wyborów k: 1, 2 lub 3. Jedna z tych nierówności będzie spełniona; pokaże ona, w którym miejscu należy dołączyć do drzewa liść l i węzeł p. W naszym przykładzie okaże się, że liść k będzie liściem 1 i węzeł p dołączymy na drodze z liścia 1 do liścia 8. Węzłowi p nadamy teraz kolejny numer, tzn. 9. Tak samo jak poprzednio wyznaczamy odległości między węzłem 9 i wierzchołkami z nim sąsiadującymi. Otrzymamy nowe drzewo:

epsffile(wys10.eps)

Teraz musimy dołączyć do drzewa następny liść, o numerze 5. Możliwe są dwa przypadki: droga od liścia 5 do zbudowanego dotychczas drzewa może ,,dołączyć się'' do krawędzi łączącej liść z sąsiednim węzłem lub do krawędzi łączącej dwa węzły. Można łatwo stwierdzić, czy ta droga dołączyła się do krawędzi wychodzącej z liścia.

Przypuśćmy, że mamy dane drzewo i dołączamy nowy liść l. Załóżmy, że droga z liścia l do drzewa dołącza się do krawędzi łączącej liść k z sąsiednim węzłem m. Oznaczmy literą n węzeł, w którym ta droga dołącza się do krawędzi łączącej k z m. Niech wreszcie i i j będą dwoma dowolnymi liśćmi naszego drzewa, różnymi od liścia k. Na następnych dwóch rysunkach widzimy możliwe położenia tych liści i węzłów (grubą linią są zaznaczone krawędzie drzewa, cienką linią drogi w drzewie i nowe krawędzie po dołączeniu liścia l i węzła n).

epsffile(wys11.eps)

epsffile(wys12.eps)

Sytuacja ta jest możliwa tylko wtedy, gdy zachodzi nierówność

 d_(i,k)+d_(j,l) > d...
Ten warunek można sprawdzić dla każdej krawędzi łączącej liść drzewa z sąsiednim węzłem. Może się jednak okazać, że żadna z tych krawędzi nie jest właściwa, czyli powyższa nierówność nie jest prawdziwa. Nowy liść musimy wtedy dołączyć do drzewa w krawędzi łączącej dwa węzły. Jak stwierdzić, która to krawędź?

Można postąpić dwojako. Przypuśćmy, że mamy dołączyć nowy liść l w węźle n znajdującym się na krawędzi łączącej dwa węzły m i k. Niech i i j będą dwoma pozostałymi sąsiadami węzła m. Możemy obliczyć odległości od liścia l do wierzchołków i, j i k (ćwiczeniem dla Czytelnika będzie, jak to zrobić). Dalej postępujemy tak samo: musi być spełniona nierówność

 d_(i,k)+d_(j,l) > d...
Można też postąpić inaczej. Na czas poszukiwania właściwej krawędzi usuwamy z drzewa krawędzie niewłaściwe. Dokładniej, przeszukujemy krawędzie łączące liście z sąsiednimi węzłami. Jeśli znajdziemy krawędź właściwą, to dołączamy nowy liść. Jeśli badana krawędź nie jest właściwa, to usuwamy ją wraz z liściem, którym ona się kończy. Jej drugi koniec może stać się teraz nowym liściem (zauważmy, że mogą ulec zmianie stopnie węzłów!). Wreszcie znajdziemy krawędź właściwą i wtedy dołączamy z powrotem krawędzie usunięte z drzewa. Ta metoda została użyta w programie wzorcowym.

Oczywiście długości krawędzi obliczamy korzystając z tych samych wzorów co poprzednio.

W ten sposób dołączamy kolejne liście i po dołączeniu ostatniego drzewo zostało zrekonstruowane. Czas działania tego algorytmu jest również rzędu O(n2).

W naszym przykładzie kolejne liście zostaną dołączone do krawędzi łączących inne liście z sąsiednimi węzłami. Na dalszych rysunkach widzimy kolejne drzewa powstające przez dołączenie następnych liści.

epsffile(wys13.eps)

epsffile(wys14.eps)

I wreszcie drzewo, o które chodziło:

epsffile(wys15.eps)

Zadanie to ma zastosowanie w genetyce do wyznaczania tzw. drzew filogenetycznych. Są to drzewa, których liśćmi są gatunki zwierząt lub roślin, a odległości wskazują, jak bardzo dane gatunki są odległe od siebie ewolucyjnie. Rekonstrukcja drzewa sugeruje możliwe kierunki ewolucji: wskazuje, które gatunki mogły powstać bezpośrednio z innych (są to gatunki połączone krawędzią).

Testy

Testy zostały stworzone automatycznie, charakteryzuje je 5 wartości, przy tworzeniu drzewa binarnego:

Jeśli procent liści jest bliski 50, to otrzymamy drzewo pełne. Jeśli bliski 0, będzie to lista. Jeśli będzie dowolny od 0 do 100 to otrzymamy drzewo losowe, czyli zrównoważone.

begin(tabular)(lcccc...