Wycieczka (omówienie)

08.08.2010

Załóżmy najpierw, że wszystkie drogi są jednego rodzaju (np. 1). Zadanie sprowadza się wtedy do odpowiedzi na pytanie: do których wierzchołków istnieje w grafie ścieżka o początku w 1 i długości D?

Załóżmy, że mamy tablicę trójwymiarową M taką, że:

  • M[u][v][D] = 1 wtedy, gdy istnieje ścieżka długości D łącząca wierzchołki u, v
  • M[u][v][D] = 0 wtedy, gdy taka ścieżka nie istnieje.


Zauważmy, że zachodzi następująca własność: M[k][l][d1+d2] = 1 wtedy i tylko wtedy, gdy istnieje przynajmniej jeden taki wierzchołek t, że: M[k][t][d1] = 1 oraz M[t][l][d2] = 1. Skoro bowiem istnieje ścieżka długości d1+d2 prowadząca z wierzchołka k do l, to po d1 krokach musi przez jakiś wierzchołek przechodzić, co dowodzi istnienia wierzchołka t.

To daje nam od razu następujący algorytm:

1. Dla każdego k mamy: M[k][k][0] = 1, reszta tablicy M[][][0] zawiera same zera.
2. M[k][l][1] = 1 wtedy i tylko wtedy, gdy istnieje krawędź prowadząca bezpośrednio z k do l.
3. Dla każdego d od 2 do D i każdej pary wierzchołków k, l oblicz:
   M[k][l][d] = max( M[k][1][d-1] * M[1][l][1], M[k][2][d-1] * M[2][l][1], ..., M[k][n][d-1] * M[n][l][1] )
4. Wypisz te wierzchołki u, dla których M[1][u][D] = 1.

Krok 3. to tak naprawdę mnożenie macierzy M[][][d-1] oraz M[][][1].
Złożoność tego algorytmu jest O(n^3 * D), czyli o wiele za dużo. Na szczęście nie musimy obliczać całej tablicy M[][][]. Wykorzystując pomysł szybkiego potęgowania możemy obliczać tylko macierze M[][][2^k] i z nich obliczyć M[][][D]. To redukuje złożoność do O(n^3 * log D).
Wróćmy jednak do oryginalnych założeń zadania. Mamy drogi różnych rodzajów, a całkowita ścieżka jest podzielona na d fragmentów. Dla każdego rodzaju dróg trzeba zatem obliczyć osobno wartości M. To daje złożoność O(d * n^3 * log D), która nie gwarantowała jeszcze maksymalnej liczby punktów.

Aby jeszcze bardziej przyspieszyć działanie algorytmu, wykorzystamy założenie n <= 60. Dzięki temu, aby pamiętać macierze M[][][x] (dla ustalonej wartości x) możemy skorzystać z masek bitowych (typ long long zajmuje 64 bity, a na pojedynczą wartość M[k][l][x] potrzeba przecież tylko jednego bitu). Tak więc cały wiersz macierzy M[][][x] może być reprezentowany jedną wartością typu long long, to samo dotyczy kolumn. Krok 3. z algorytmu można teraz zapisać jako:

M[k][l][x] = wiersz[k][x-1] & kolumna[l][1]

co daje zadowalającą złożoność O(d * n^2 * log D).

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com