Kreczmar Dzien 3

Omowienie zadan 2006-07-22
Dzien 3

1. Najwiecej Radosci

W grafie znalezc droge o dlugosci dokladnie M krawedzi, taka zeby sumaryczny koszt byl jak najwiekszy.

Chociaz zadanie z pozoru wydaje sie byc grafowe, wcale takim nie jest. Ograniczenia w zadania pozwalaja zastosowac macierz sasiedzctwa zamiast list sasiedztwa.

Teraz rozpatrujemy problem ogolniejszy, znajdujemy takie drogi pomiedzy kazda para wierzcholkow.

Tu nasuwa sie algorytm Belmana-Forda. Trzeba go iterowac tyle razy, ile ma miec dlugosc sciezka. Zeby zmniejszyc zlozonosc stosujemy algorytm optymalnego mnozenia macierz.

Zlozonosc: O(n^2*lgT)
Klasa: srednio grafowe (zgodnie z zyczeniem )

2. Gory

Znajdowanie najdluzszego podciagu nierosnacego w czasie O(n*lgn).
(mozna to znalezc w jakis madrych i fajnych ksiazkach).

Klasa: dynamik

Tutaj ten algorytm wystarczy zmodyfikowac, zeby oprocz dlugosci pamietal tez ciekawosc i wybieral sposrod sciezek o rownej dlugosci te ciekawsze.

(C++: sprytne zastosowanie map z STL)

3. Spalic sieci

Zadanie, w ktorym koncowy rezultat zalezal od tego co przyslali uczestnicy. Sprawdzanie Tomasza Kulczynskiego: O(n(n+n))

Leave a Comment

Name:
E-mail:
URI:
Enter this code: