43591506：最小圈

题目描述

原题来自：HNOI 2009
考虑带权的有向图G=(V,E)G=(V,E) 以及w:E→Rw:E→R ，每条边e=(i,j)(i≠j,i∈V,j∈V)e=(i,j)(i≠j,i∈V,j∈V) 的权值定义为Wi,jWi,j ，令n=∣V|n=∣V| 。c=(c1,c2,⋯,ck)(ci∈V)c=(c1,c2,⋯,ck)(ci∈V) 是GG 中的一个圈当且仅当(ci,ci+1)(1≤i<k)(ci,ci+1)(1≤i<k) 和(ck,c1)(ck,c1) 都在EE 中，这时称kk 为圈cc 的长度。同时令ck+1=c1ck+1=c1 ，并定义圈c=(c1,c2,⋯,ck)c=(c1,c2,⋯,ck) 的平均值为：

μ (c)=1/k\sum i=1 k w c i, c i+1

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

输入格式:

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

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

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

输出格式:

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

输入样例复制

输出样例 复制

3.66666667

说明

样例输入2:

2 2
1 2 -2.9
2 1 -3.1

样例输出2:

-3.00000000

数据范围：

对于 20% 的数据，1≤n≤100,1≤m≤1000；

对于 40% 的数据，1≤n≤1000,1≤m≤5000；

对于 100% 的数据，1≤n≤3000,1≤m≤104,∣wi,j∣≤107 。

输入保证1≤i,j≤n。