In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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).