本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1120. 【spfa算法】最小圈


Description

考虑带权的有向图G=(V,E)以及w:E->R,每条边e=(i,j)(i≠j,i∈V,j∈V)的权值定义为wij,令n=|V|。c=(c1,c2,...,ck)(ci∈V)是G中的一个圈当且仅当(ci,ci+1)(1≤i<k)和(ck,c1)都在E中,这时称k为圈c的长度同时令ck+1=c1,并定义圈c=(c1,c2,...,ck)的平均值为,即c上所有边的权值的平均值。令为G中所有圈c的平均值的最小值。现在的目标是:在给定了一个图G=(V,E)以及w:E->R之后,求出G中所有圈c的平均值的最小值

Input

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

Output

仅包含一个实数,要求输出到小数点后8位。

Samples

Input Copy
4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3
Output
3.66666667

Source

信息学奥赛一本通·提高篇
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags:
Contests involved

1015. 信息学奥赛一本通提高篇 图论(spfa算法)
My history solutions

You didn't submit any solution!
Submit your solution

Login Register