![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Marcin Kubica (treść, opracowanie) Marek Pawlicki (program wzorcowy) NarciarzeDrużyna narciarska organizuje trening na Bajtogórze. Na północnym stoku góry znajduje się jeden wyciąg. Wszystkie trasy prowadzą od górnej do dolnej stacji wyciągu. W trakcie treningu członkowie drużyny będą razem startować z górnej stacji wyciągu i spotykać się przy dolnej stacji. Poza tymi dwoma punktami trasy, zawodników nie mogą się przecinać, ani stykać. Wszystkie trasy muszą cały czas prowadzić w dół. Mapa tras narciarskich składa się z sieci polan połączonych przecinkami. Każda polana leży na innej wysokości. Dwie polany mogą być bezpośrednio połączone co najwyżej jedną przecinką. Zjeżdżając od górnej do dolnej stacji wyciągu można tak wybrać drogę, żeby odwiedzić dowolną polanę (choć być może nie wszystkie w jednym zjeździe). Trasy narciarskie mogą się przecinać tylko na polanach i nie prowadzą przez tunele, ani estakady. ZadanieNapisz program, który:
WejścieW pierwszym wierszu pliku wejściowego NAR.IN znajduje się jedna liczba całkowita n równa liczbie polan, W każdym z kolejnych n-1 wierszy znajduje się ciąg liczb całkowitych pooddzielanych pojedynczymi odstępami. Liczby w (i+1)-szym wierszu pliku określają, do których polan prowadzą w dół przecinki od polany nr i. Pierwsza liczba k w wierszu określa liczbę tych polan, a kolejne k liczb to ich numery, które są uporządkowane wg ułożenia prowadzących do nich przecinek w kierunku ze wschodu na zachód. Polany są ponumerowane liczbami od 1 do n. Górna stacja wyciągu znajduje się na polanie numer 1, a dolna na polanie numer n. WyjścieW pierwszym i jedynym wierszu pliku wyjściowego NAR.OUT powinna znajdować się dokładnie jedna liczba całkowita - maksymalna liczba narciarzy mogących wziąć udział w treningu. PrzykładDla pliku wejściowego NAR.IN15 5 3 5 9 2 4 1 9 2 7 5 2 6 8 1 7 1 10 2 14 11 2 10 12 2 13 10 3 13 15 12 2 14 15 1 15 1 15 1 15poprawną odpowiedzią jest plik wyjściowy NAR.OUT 3 RozwiązanieZadanie to możemy sformułować w języku teorii grafów. Mamy dany acykliczny, planarny graf skierowany - wierzchołki tego grafu to polany i stacje wyciągu, a krawędzie to przecinki. W grafie tym mamy wyróżnione dwa wierzchołki reprezentujące górną i dolną stację wyciągu. Z górnej stacji wyciągu osiągalne są wszystkie wierzchołki w grafie. Podobnie, z każdego wierzchołka w grafie osiągalna jest dolna stacja wyciągu. Ponadto stacje wyciągu (jako najwyżej i najniżej położone wierzchołki) znajdują się na obwodzie grafu. Należy wyznaczyć maksymalną liczbę k takich ścieżek w grafie, które prowadzą od górnej do dolnej stacji wyciągu i poza stacjami wyciągu nie mają (parami) żadnych wspólnych wierzchołków. Załóżmy chwilowo, że w grafie nie ma krawędzi łączącej bezpośrednio górną i dolną stację wyciągu. Jeżeli taka krawędź jest, to możemy ją usunąć, obliczyć wynik, po czym zwiększyć go o 1. Zadanie to możemy rozwiązać za pomocą algorytmu zachłannego. Wyobraźmy sobie, że wybraliśmy k ścieżek spełniających warunki zadania. Oznaczmy te ścieżki, od lewej do prawej (ze wschodu na zachód), przez s_1, ..., s_k. Zauważmy, że bez łamania warunków zadania możemy przesunąć skrajnie lewą (wschodnią) ścieżkę s1 w lewo tak, aby prowadziła przez wierzchołki leżące na lewym pół-obwodzie grafu. ![]() Tak więc, bez zmniejszenia ogólności, możemy przyjąć, że s1 biegnie przez wierzchołki leżące na lewym pół-obwodzie grafu (zobacz rysunek 1). Podobnie możemy poprzesuwać pozostałe ścieżki. Zauważmy, że wśród wszystkich możliwych ścieżek, które prowadzą od górnej do dolnej stacji wyciągu i nie mają (za wyjątkiem stacji wyciągu) wspólnych wierzchołków z s1, istnieje skrajnie lewa ścieżka. Bez naruszenia warunków zadania możemy przyjąć, że s2 jest właśnie taką ścieżką. Analogicznie ustalamy kolejne ścieżki. Przyjmujemy, że si jest skrajnie lewą spośród wszystkich możliwych ścieżek, które prowadzą od górnej do dolnej stacji wyciągu i nie mają (za wyjątkiem stacji wyciągu) wspólnych wierzchołków z żadną ze ścieżek Wyłania się następujący schemat algorytmu:
Pozostał do rozwiązania problem jak wyznaczyć skrajnie lewą ścieżkę w odpowiednim podgrafie zadanego grafu. Ścieżkę taką konstruujemy począwszy od górnej stacji wyciągu, korzystając z procedury przeszukiwania grafu w głąb (zobacz [13] lub [13]). Ważne jest, aby w trakcie przeszukiwania przeglądać krawędzie wychodzące z danego wierzchołka w kolejności od lewej do prawej (ze wschodu na zachód), czyli zgodnie z kolejnością, w jakiej zostały one podane w pliku wejściowym. W momencie osiągnięcia dolnej stacji wyciągu przerywamy przeszukiwanie - szukana ścieżka znajduje się wówczas na stosie. W trakcie przeszukiwania grafu kolorujemy odwiedzone wierzchołki. Zauważmy, że pokolorowane zostają wierzchołki tworzące skonstruowaną ścieżkę oraz niektóre wierzchołki leżące na lewo od tej ścieżki. Konstruując kolejne ścieżki omijamy wierzchołki już pokolorowane (za wyjątkiem stacji wyciągu). Powyższy algorytm znajdowania skrajnie lewej ścieżki można zaimplementować w następujący sposób.
Szukaną liczbę ścieżek możemy wyznaczyć w następujący sposób:
Z twierdzenia Eulera wiadomo (zobacz [10]), że w każdym spójnym grafie planarnym liczba krawędzi m jest takiego rzędu jak liczba wierzchołków n. Dokładniej, dla Sprawdzenie, czy w grafie jest krawędź łącząca bezpośrednio górną i dolną krawędź wyciągu wymaga przejrzenia wszystkich krawędzi wychodzących z górnej stacji wyciągu. Tak więc złożoność czasowa tej operacji jest rzędu n. Zauważmy, że w trakcie przeglądania grafu po każdej krawędzi przechodzimy co najwyżej raz. Stąd, złożoność czasowa przeszukiwania grafu jest rzędu n. Tak więc, złożoność czasowa całego rozwiązania jest rzędu n. TestyDo sprawdzenia rozwiązań zawodników użyto 8-miu testów. Testy te można podzielić na trzy grupy: W poniższej tabelce podano wielkości i wyniki dla poszczególnych testów. ![]() |