P3199 [HNOI2009] Minimum Mean Cycle

Consider a weighted directed graph $G=(V,E)$ and $w: E \rightarrow \mathbb{R}$. Each edge $e=(i,j)$ ($i \neq j$, $i, j \in V$) has weight $w_{i,j}$. Let $n = |V|$. A sequence $c=(c_1, c_2, \cdots, c_k)$ ($c_i \in V$) is a cycle in $G$ if and only if $(c_i, c_{i+1})$ ($1 \le i < k$) and $(c_k, c_1)$ are both in $E$. We call $k$ the length of cycle $c$, and set $c_{k+1} = c_1$. The average value of cycle $c=(c_1, c_2, \cdots, c_k)$ is defined as $$ \mu(c)= \frac 1 k \sum\limits_{i=1}^{k} w_{c_i,c_{i+1}}. $$ Let $\mu'(G)=\min_c \mu(c)$ be the minimum average value over all cycles $c$ in $G$. Given $G=(V,E)$ and $w: E \rightarrow \mathbb{R}$, compute the minimum average value $\mu'(G)$ over all cycles $c$ in $G$.

The first line contains two positive integers $n$ and $m$, separated by a space. Here $n = |V|$ and $m = |E|$ denote the number of vertices and edges, respectively. The next $m$ lines each contain three numbers $i, j, w_{i,j}$, indicating there is an edge $(i, j)$ with weight $w_{i,j}$. Note that edge weights can be real numbers. The input guarantees that the graph $G=(V,E)$ is connected, contains at least one cycle, and there exists a vertex that can reach all other vertices.

Output a real number $\mu'(G)$, printed with $8$ digits after the decimal point.

- Constraints: For $100\%$ of the testdata, $2 \le n \le 3000$, $1 \le m \le 10000$, $|w_{i,j}| \le 10^7$, $1 \le i, j \le n$ and $i \neq j$. - Note: There exists an $O(nm)$ solution; an $O(nm \log n)$ solution also passes. Translated by ChatGPT 5