最小圈
Description
【题目简述】
对于一张有向图,要你求图中最小圈的平均值最小是多少,即若一个圈经过k个结点,那么一个圈的平均值为圈上K条边权的和除以k。现要求其中的最小值。
Format
Input
第一行2个正整数,分别为n和m,并用一个空格隔开,只用n=|V|,m=|E|分别表示图中有n个点,m条边。
以下m行,每行3个数i,j,w[i,j],表示有一条边(i,j)且该边的权值为w[i,j]。输入数据保证图G=(V,E)连通,存在圈且有一个点能到达其他点。
Output
一行一个数,表示最小圈的值,保留8位小数。
Sample 1
Input
4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3
Output
3.66666667
Sample 2
Input
2 2
1 2 -2.9
2 1 -3.1
Output
-3.00000000
Limitation
1s, 64MiB for each test case.
对于20%的数据,n<=100,m<=1000;
对于40%的数据,n<=1000,m<=5000;
对于100%的数据,n<=3000,m<=10000;
对于100%的数据,|w[i,j]|<=10^7;
Source
bzoj1486
信息
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 7
- 已通过
- 4
- 通过率
- 57%
- 上传者