问题 A: 1.[HNOI2009]最小圈(Bzoj1486)

问题 A: 1.[HNOI2009]最小圈(Bzoj1486)

题目描述

  对于一张有向图,要你求图中最小圈的平均值最小是多少,即若一个圈经过k个结点,那么一个圈的平均值为圈上k条边权的和除以k,现要求其中的最小值。

输入

第一行2个正整数,分别为n和m,并用一个空格隔开,只用n=|V|,m=|E|分别表示图中有n个点,m条边。
以下m行,每行3个数i,j,wij,表示有一条边(i,j)且该边的权值为wij。输入数据保证图G=(V,E)连通,存在圈且有一个点能到达其他点。

输出

一行一个数,表示最小圈的值,保留8位小数。

样例输入输出

输入#1 复制
4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3
输出#1 复制
3.66666667

提示

对于20%的数据,n ≤ 100,m≤1 000。
对于40%的数据,n ≤ 1000,m5 000。
对于100%的数据,n ≤ 3000,m10 000。
对于100%的数据,|wij| ≤ 107

序号 标题 作者 发表时间 费用 订购数 操作