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

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

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

原题来自:HNOI 2009

考虑带权的有向图 G=(V,E)G=(V,E)G=(V,E) 以及 w:E→Rw:E\to Rw:ER,每条边 e=(i,j)(i̸=j,i∈V,j∈V)e=(i,j)(i\not =j,i\in V,j\in V)e=(i,j)(i̸=j,iV,jV) 的权值定义为 wi,jw_{i,j}wi,j,令 n=∣V∣n=|V|n=Vc=(c1,c2,⋯ ,ck)(ci∈V)c=(c_1,c_2,\cdots ,c_k)(c_i\in V)c=(c1,c2,,ck)(ciV)GGG 中的一个圈当且仅当 (ci,ci+1)(1≤i(ci,ci+1)(1i<k)(ck,c1)(c_k,c_1)(ck,c1) 都在 EEE 中,这时称 kkk 为圈 ccc 的长度。同时令 ck+1=c1c_{k+1}=c_1ck+1=c1,并定义圈 c=(c1,c2,⋯ ,ck)c=(c_1,c_2,\cdots ,c_k)c=(c1,c2,,ck) 的平均值为:

μ(c)=1k∑i=1kwci,ci+1\mu (c)=\frac{1}{k}\sum_{i=1}^k w_{c_i,c_{i+1}}μ(c)=k1i=1kwci,ci+1

ccc 上所有边的权值的平均值。

μ∗(c)=min⁡{μ(c)}\mu^*(c)=\min \{\mu (c)\}μ(c)=min{μ(c)}GGG 中所有圈 ccc 的平均值的最小值。现在的目标是:在给定了一个图 G=(V,E)G=(V,E)G=(V,E) 以及 w:E→Rw:E\to Rw:ER 之后,请求出 GGG 中所有圈 ccc 的平均值的最小值 μ∗(c)=min⁡{μ(c)}\mu ^* (c)=\min \{ \mu (c)\}μ(c)=min{μ(c)}


Input

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

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

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


Output

仅包含一个实数 μ∗=min⁡{μ(c)}\mu ^*=\min \{ \mu (c) \}μ=min{μ(c)},要求输出到小数点后 888 位。


Sample Input

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

Sample Output

3.66666667

HINT

对于 20%20\%20% 的数据,1≤n≤100,1≤m≤10001\le n\le 100,1\le m\le 10001n100,1m1000
对于 40%40\%40% 的数据,1≤n≤1000,1≤m≤50001\le n\le 1000,1\le m\le 50001n1000,1m5000
对于 100%100\%100% 的数据,1≤n≤3000,1≤m≤104,∣wi,j∣≤1071\le n\le 3000,1\le m\le 10^4,|w_{i,j}|\le 10^71n3000,1m104,wi,j107

输入保证 1≤i,j≤n1\le i,j\le n1i,jn


Source/Category


Submit Status