luogu#P3199. [HNOI2009] 最小圈

    ID: 7229 远端评测题 5000ms 512MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>2009湖南深度优先搜索DFSSPFA分数规划

[HNOI2009] 最小圈

题目描述

考虑带权有向图 G=(V,E)G=(V,E) 以及 w:ERw:E\rightarrow \R,每条边 e=(i,j)e=(i,j)iji\neq ji,jVi, j\in V)的权值定义为 wi,jw_{i,j}。设 n=Vn=|V|

c=(c1,c2,,ck)c=(c_1,c_2,\cdots,c_k)ciVc_i\in V)是 GG 中的一个圈当且仅当 (ci,ci+1)(c_i,c_{i+1})1i<k1\le i<k)和 (ck,c1)(c_k,c_1) 都在 EE 中。称 kk 为圈 cc 的长度,同时记 ck+1=c1c_{k+1}=c_1,并定义圈 c=(c1,c2,,ck)c=(c_1,c_2,\cdots,c_k) 的平均值为

$$\mu(c)= \frac 1 k \sum\limits_{i=1}^{k} w_{c_i,c_{i+1}} $$

cc 上所有边的权值的平均值。设 μ(G)=mincμ(c)\mu'(G)=\min_c\mu(c)GG 中所有圈 cc 的平均值的最小值。

给定图 G=(V,E)G=(V,E) 以及 w:ERw:E\rightarrow \R,求出 GG 中所有圈 cc 的平均值的最小值 μ(G)\mu'(G)

输入格式

第一行两个正整数,分别为 nnmm,并用一个空格隔开。其中 n=Vn=|V|m=Em=|E| 分别表示图中有 nn 个点 和 mm 条边。

接下来 mm 行,每行三个数 i,j,wi,ji,j,w_{i,j},表示有一条边 (i,j)(i,j) 且该边的权值为 wi,jw_{i,j},注意边权可以是实数。输入数据保证图 G=(V,E)G=(V,E) 连通,存在圈且有一个点能到达其他所有点。

输出格式

一个实数 μ(G)\mu'(G),要求精确到小数点后 88 位。

4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3
3.66666667
2 2
1 2 -2.9
2 1 -3.1
-3.00000000

提示

对于 100%100\% 的数据,2n30002\leq n\le 30001m100001\leq m\le 10000wi,j107|w_{i,j}| \le 10^71i,jn1\leq i, j\leq niji\neq j


提示:本题存在 O(nm)O(nm) 的做法,但是 O(nmlogn)O(nm\log n) 的做法也可以通过。