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

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

题目描述

原题来自:HNOI 2009

考虑带权的有向图 G=(V,E)G=(V,E) 以及 w:ERw:E\to R,每条边 e=(i,j)(ij,iV,jV)e=(i,j)(i\not =j,i\in V,j\in V) 的权值定义为 wi,jw_{i,j},令 n=Vn=|V|c=(c1,c2,,ck)(ciV)c=(c_1,c_2,\cdots ,c_k)(c_i\in V)GG 中的一个圈当且仅当 (ci,ci+1)(1i<k)(c_i,c_{i+1})(1\le i\lt 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) 的平均值为:

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

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

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

输入格式

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

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

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

输出格式

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

样例 1

4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3
3.66666667
2 2
1 2 -2.9
2 1 -3.1
-3.00000000

数据范围与提示

对于 20%20\% 的数据,1n100,1m10001\le n\le 100,1\le m\le 1000
对于 40%40\% 的数据,1n1000,1m50001\le n\le 1000,1\le m\le 5000
对于 100%100\% 的数据,1n3000,1m104,wi,j1071\le n\le 3000,1\le m\le 10^4,|w_{i,j}|\le 10^7

输入保证 1i,jn1\le i,j\le n