题目描述
原题来自：HNOI 2009
考虑带权的有向图
G=(V,E)
G=(V,E) 以及
w:E\to R
w:E→R，每条边
e=(i,j)(i\not =j,i\in V,j\in V)
e=(i,j)(i!=j,i∈V,j∈V) 的权值定义为
w_{i,j}
wi,j
，令
n=|V|
n=∣V∣。
c=(c_1,c_2,\cdots ,c_k)(c_i\in V)
c=(c1
,c2
,⋯,ck
)(ci
∈V) 是
G
G 中的一个圈当且仅当
(c_i,c_{i+1})(1\le i\lt k)
(ci
,ci+1
)(1≤i(c_k,c_1)
(ck
,c1
) 都在
E
E 中，这时称
k
k 为圈
c
c 的长度。同时令
c_{k+1}=c_1
ck+1
=c1
，并定义圈
c=(c_1,c_2,\cdots ,c_k)
c=(c1
,c2
,⋯,ck
) 的平均值为：
μ(c)=1/k*∑wci,ci+1
(i=1->k)
即
c
c 上所有边的权值的平均值。
令
\mu^*(c)=\min \{\mu (c)\}
μ∗(c)=min{μ(c)} 为
G
G 中所有圈
c
c 的平均值的最小值。现在的目标是：在给定了一个图
G=(V,E)
G=(V,E) 以及
w:E\to R
w:E→R 之后，请求出
G
G 中所有圈
c
c 的平均值的最小值
\mu ^* (c)=\min \{ \mu (c)\}
μ∗(c)=min{μ(c)}。
输入
第一行包含两个正整数
n
n 和
m
m，并用一个空格隔开，其中
n=|V|,m=|E|
n=∣V∣,m=∣E∣，分别表示图中有
n
n 个顶点和
m
m 条边；
接下来
m
m 行，每行包含用空格隔开的三个数
i,j,w_{i,j}
i,j,wi,j
，表示有一条边
(i,j)
(i,j) 且该边的权值为
w_{i,j}
wi,j
。
输入数据保证图
G=(V,E)
G=(V,E) 连通，存在圈且有一个点能到达其他所有点。
输出
仅包含一个实数
\mu ^*=\min \{ \mu (c) \}
μ∗=min{μ(c)}，要求输出到小数点后
8
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
提示
对于20% 的数据，1≤n≤100,1≤m≤1000；
对于40% 的数据，1≤n≤1000,1≤m≤5000；
对于100% 的数据，1≤n≤3000,1≤m≤104 , ∣wi,j ∣≤107。
输入保证 1≤i,j≤n。
来源/分类
ybttg 负环 二分 分数规划