W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Masz podany skierowany graf z wagami na krawędziach. Twoim zadaniem jest znalezienie cyklu w tym grafie o jak największej średniej wadze krawędzi.
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite (), oznaczające odpowiednio liczbę wierzchołków oraz krawędzi grafu. W kolejnych wierszach znajduje się opis kolejnych krawędzi w postaci trzech liczb (). Oznacza to że istnieje krawędź z wierzchołka do wierzchołka o wadze krawędzi . Między każdą parą wierzchołków będzie istniała co najwyżej jedna krawędź w każdą stronę.
W pierwszym i jedynym wierszu wyjścia powinna się znajdować jedna liczba rzeczywista, równa maksymalnej średniej wadze cyklu w podanym grafie. Liczba ta powinna być zapisana z dokładnością do 4 miejsc po przecinku. Możesz założyć że w grafie zawsze będzie istniał jakiś cykl.
Dla danych wejściowych:
5 6 1 2 6 2 3 2 3 1 3 2 4 1 4 2 5 5 4 100
poprawną odpowiedzią jest:
3.6667
Autor zadania: Adrian Jaskółka (zapożyczenie).