6719: 最小圈
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
考虑带圈的有向图G=(V，E)以及w:E→R，每条边e=(i，j)(i<>j,i∈V)的权值定义为w[i,j]，令n=|V|。C=(c1,c2,…,ck)(ci∈V)是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=(V，E）以及w：E→R之后，请求出G中所有圈c的平均值的最小值
输入
第一行包含两个整数n和m，并用一个空格隔开，其中n=|V|，m=|E|分别表示途中有n个点和m条边。接下来m行，每行包含用空格隔开的三个数i，j和w[i,j]，表示有一条边(i,j)且该边的权值为w[i,j]。输入数据保证图G=(V,E)连通，存在圈且有一个点能到达其他所有点。
输出
仅包含一个实数
，要求输出到小数点后8位。
，要求输出到小数点后8位。样例输入 复制
4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3
样例输出 复制
3.66666667
提示
【样例说明】
样例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。