1506：最小圈

题目描述

考虑带权的有向图 $G=(V,E)$ 以及边权函数 $w:E \to \mathbb{R}$，每条边 $e=(i,j)\ (i \ne j, i \in V, j \in V)$ 的权值定义为 $w_{i,j}$。令 $n=|V|$。$c=(c_1,c_2,\cdots,c_k)\ (c_i \in V)$ 是 $G$ 中的一个圈当且仅当 $(c_i,c_{i+1})\ (1 \le i < k)$ 和 $(c_k,c_1)$ 都在 $E$ 中，这时称 $k$ 为圈 $c$ 的长度。同时令 $c_{k+1}=c_1$，并定义圈 $c=(c_1,c_2,\cdots,c_k)$ 的平均值为：

$$\mu(c) = \frac{1}{k} \sum_{i=1}^{k} w_{c_i,c_{i+1}}$$

即 $c$ 上所有边的权值的平均值。

令 $\mu^*(c) = \min\{\mu(c)\}$ 为 $G$ 中所有圈 $c$ 的平均值的最小值。现在的目标是：在给定了一个图 $G=(V,E)$ 以及 $w:E \to \mathbb{R}$ 之后，请求出 $G$ 中所有圈 $c$ 的平均值的最小值 $\mu^*(c) = \min\{\mu(c)\}$。

输入格式

第一行包含两个正整数 $n$ 和 $m$，并用一个空格隔开，其中 $n=|V|, m=|E|$，分别表示图中有 $n$ 个顶点和 $m$ 条边；

接下来 $m$ 行，每行包含用空格隔开的三个数 $i, j, w_{i,j}$，表示有一条边 $(i,j)$ 且该边的权值为 $w_{i,j}$。

输入数据保证图 $G=(V,E)$ 连通，存在圈且有一个点能到达其他所有点。

输出格式

仅包含一个实数 $\mu^* = \min\{\mu(c)\}$，要求输出到小数点后 $8$ 位。

样例

样例输入 #1

4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3

样例输出 #1

3.66666667

样例解释 #1

• $n=4$，$m=5$。
• 边：
  1. $1 \to 2$ 权值 $5$
  2. $2 \to 3$ 权值 $5$
  3. $3 \to 1$ 权值 $5$
  4. $2 \to 4$ 权值 $3$
  5. $4 \to 1$ 权值 $3$
• 图中的圈有：
  1. 圈 $1 \to 2 \to 3 \to 1$：长度 $3$，总权值 $5+5+5=15$，平均值 $15/3=5$。
  2. 圈 $1 \to 2 \to 4 \to 1$：长度 $3$，总权值 $5+3+3=11$，平均值 $11/3 \approx 3.66666667$。
  3. 可能还有更长的圈，但平均值可能更小。
• 最小平均值是圈 $1 \to 2 \to 4 \to 1$ 的 $11/3 \approx 3.66666667$。

样例输入 #2

2 2
1 2 -2.9
2 1 -3.1

样例输出 #2

-3.00000000

样例解释 #2

• 圈 $1 \to 2 \to 1$：长度 $2$，总权值 $-2.9 + (-3.1) = -6$，平均值 $-6/2 = -3$。
• 最小平均值就是 $-3$。

数据范围

• 对于 $20\%$ 的数据，$1 \le n \le 100, 1 \le m \le 1000$
• 对于 $40\%$ 的数据，$1 \le n \le 1000, 1 \le m \le 5000$
• 对于 $100\%$ 的数据，$1 \le n \le 3000, 1 \le m \le 10^4, |w_{i,j}| \le 10^7$

输入保证 $1 \le i, j \le n$。

时空限制

• 时间限制：1000 ms
• 内存限制：65536 KB

注意：本题是典型的最小平均值环问题，可以使用分数规划（二分答案）结合 SPFA 判断是否存在负环（将边权减去 mid 后判断是否有负环）。由于 $n \le 3000$，$m \le 10^4$，二分答案加 SPFA 判负环在合理优化下可以通过。