「一本通 3.3 练习 1」最小圈

【题目描述】

原题来自：HNOI 2009

考虑带权的有向图 $G=(V,E)$ 以及 $w:E\to R$ ，每条边 $e=(i,j)(i\neq j,i\in V,j\in V)$ 的权值定义为 $W_{i,j}$ ，令 $n=∣V |$ 。 $c=(c_1,c_2,\dots,c_k)(c_i\in V)$ 是 $G$ 中的一个圈当且仅当 $(c_i,c_{i+1})(1≤i

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

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

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

【输入】

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

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

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

【输出】

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

【输入样例】

【输出样例】

3.66666667

【提示】

样例输入2:

2 2
1 2 -2.9
2 1 -3.1

样例输出2:

\-3.00000000

数据范围：

对于 20% 的数据， $1\leq n\leq 100,1\leq m\leq 1000$ ；

对于 40% 的数据， $1\leq n\leq 1000,1\leq m\leq 5000$ ；

对于 100% 的数据， $1\leq n\leq 3000,1\leq m\leq 10^4,∣w_{i,j}∣\leq 10^7$ 。

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

【来源】

一本通在线评测