Problem1649--最小圈

1649: 最小圈

Time Limit: 1.000 Sec  Memory Limit: 128 MB
Submit: 7  Solved: 6
[Submit] [Status] [Web Board] [Creator:]

Description

考虑带圈的有向图G=(VE)以及w:ER,每条边e=(ij)(i<>j,iV)的权值定义为w[i,j],令n=|V|C=(c1,c2,,ck)(ciV)G中的一个圈当且仅当(c[i],c[i+1])(1<=i<k)(c[k],c[1])都在E中,这是称k为圈c的长度同时令c[k+1]=c[1],并定义圈c=(c1,c2,,ck)的平均值为,即c上所有边的权值的平均值。令G中所有圈c的平均值的最小值。现在的目标是:在给定了一个图G=(VE)以及wER之后,请求出G中所有圈c的平均值的最小值


Input

第一行包含两个整数nm,并用一个空格隔开,其中n=|V|m=|E|分别表示途中有n个点和m条边。接下来m行,每行包含用空格隔开的三个数ijw[i,j],表示有一条边(i,j)且该边的权值为w[i,j]。输入数据保证图G=(V,E)连通,存在圈且有一个点能到达其他所有点。

Output

仅包含一个实数,要求输出到小数点后8位。

Sample Input

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

Sample Output

3.66666667

HINT

 【样例说明】

样例1中共有2个圈(1,2,3)(1,2,4)。其中第一个圈的平均值为5,第二个圈的平均值为11/3。样例2中存在一个负圈。

【数据范围及约定】

20%的数据:n<=100,m<=1000

50%的数据:n<=1000,m<=5000

100%的数据:n<=3000,m<=10000

100%的数据:|w[i,j]|<=10^7


Source/Category


[Submit] [Status]