#P1486. [HNOI2009]最小圈

[HNOI2009]最小圈

[HNOI2009] 最小圈

题目描述

考虑带权的有向图 G=(V,E)G=(V,E) 以及 w:E→Rw:E\rightarrow R,每条边 e=(i,j)(i≠j,i∈V,j∈V)e=(i,j)(i\neq j,i\in V,j\in V) 的权值定义为wi,jw_{i,j},令n=∣V∣n=|V|。c=(c1,c2,⋯ ,ck)(ci∈V)c=(c_1,c_2,\cdots,c_k)(c_i\in V) 是 GG 中的一个圈当且仅当 (ci,ci+1)(1≤i<k)(c_i,c_{i+1})(1\le i<k) 和 (ck,c1)(c_k,c_1) 都在 EE 中,这时称 kk 为圈 cc 的长度同时令 ck+1=c1c_{k+1}=c_1,并定义圈 c=(c1,c2,⋯ ,ck)c=(c_1,c_2,\cdots,c_k) 的平均值为 $\mu(c)=\dfrac{\sum\limits_{i=1}^{k} w_{c_i,c_{i+1}}}{k}$,即 cc 上所有边的权值的平均值。令 μ′(c)=Min(μ(c))\mu'(c)=Min(\mu(c)) 为 GG中所有圈 cc 的平均值的最小值。现在的目标是:在给定了一个图 G=(V,E)G=(V,E) 以及 w:E→Rw:E\rightarrow R 之后,请求出 GG 中所有圈 cc 的平均值的最小值 μ′(c)=Min(μ(c))\mu'(c)=Min(\mu(c))

输入格式

第一行2个正整数,分别为 nn 和 mm,并用一个空格隔开,只用 n=∣V∣,m=∣E∣n=|V|,m=|E| 分别表示图中有 nn 个点 mm 条边。 接下来 mm 行,每行3个数 i,j,wi,ji,j,w_{i,j},表示有一条边 ⟨i,j⟩\langle i,j\rangle 且该边的权值为 wi,jw_{i,j}。输入数据保证图 G=(V,E)G=(V,E) 连通,存在圈且有一个点能到达其他所有点。

输出格式

请输出一个实数 μ′(c)=Min(μ(c))\mu'(c)=Min(\mu(c)),要求输出到小数点后8位。

样例 #1

样例输入 #1

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

样例输出 #1

3.66666667

样例 #2

样例输入 #2

2 2
1 2 -2.9
2 1 -3.1

样例输出 #2

-3.00000000

提示

对于100%的数据,n≤3000,m≤10000,∣wi,j∣≤107n\le 3000,m\le 10000,|w_{i,j}| \le 10^7