P10150: 最小圈
传统题
1.000s
时间限制
128MB
内存限制
3 提交
3 解决
【题目描述】
考虑带圈的有向图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位。 【样例输入】复制
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。