시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 6 | 0 | 0 | 0.000% |
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 n, m (2 ≤ n ≤ 100, 2 ≤ m ≤ 104), oznaczające odpowiednio liczbę wierzchołków oraz krawędzi grafu. W kolejnych m wierszach znajduje się opis kolejnych krawędzi w postaci trzech liczb a, b, c (1 ≤ a, b ≤ n, a ≠ b, 0 ≤ c ≤ 106). Oznacza to że istnieje krawędź z wierzchołka a do wierzchołka b o wadze krawędzi c. 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.
5 6 1 2 6 2 3 2 3 1 3 2 4 1 4 2 5 5 4 100
3.6667