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

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 1bentong

题目描述

原题来自:HNOI 2009

考虑带权的有向图 G=(V,E) 以及 w:E\to R ,每条边 e=(i,j)(i\not =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\lt 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 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

样例输入 2

2 2
1 2 -2.9
2 1 -3.1

样例输出 2

-3.00000000

数据范围与提示

对于 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