P96584

最小圈

难度 未定
讨论 统计 1通过 1提交 100%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

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

输入

15654215492319.png

输出

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

样例

样例 1
输入
4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3
输出
3.66666667
样例 2
输入
2 2
1 2 -2.9
2 1 -3.1
输出
-3.00000000

提示

【数据规模】

对于20%的数据,n≤100,m≤1000。

对于40%的数据,n≤1000,m≤5000。

对于100%的数据,n≤3000,m≤10000。

对于100%的数据,wij的绝对值小于等于10的7次方。

来源

一本通

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交