最小圈

题目描述:

虑带权的有向图G=(V,E)以及w:E→R，每条边e=(I,j)(i≠j,i∈V,i∈V)的权值定义为wi,j，令n=|V|。c=(c1,c2,…,ck)(ci∈V)是G中的一个圈当且仅当（ci,ci+1）(1<=i<k)和(ck,c1)都在E中，这是称k为圈c的长度同时令ck+1=c1，并定义圈成（c1,c2,….,ck）的平均值μ(c)=(Wc1,c2+ Wc2,c3+…+ Wck,ck+1)/k，即c上所有边的权值的平均值。令μ*(c)=Min{μ(c)}为G中所有圈c的平均值的最小值。现在的目标是：在给定了一个图G=(V,E)以及w:E→R之后，请求出G中所有圈c的平均值的最小值μ*(c)=Min{μ(c)}。

输入格式:

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

输出格式:

仅包含一个实数μ*(c)=Min{μ(c)}，要求输出到小数点后8位。

样例输入:

样例1：
4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3

样例2：
2 2
1 2 -2.9
2 1 -3.1

样例输出:

样例1：
3.66666667

样例2：
-3.00000000

提示:

对于100%的数据，n≤3000,m≤10000,∣wi,j​∣≤1e7

时间限制: 1000ms
空间限制: 256MB

---

来源: HNoi2009