OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【HNOI2009】最小圈

【题目描述】

考虑带权的有向图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)=sigma(w(ci,ci+1))/k,即c上所有边的权值的平均值。令μ*(c)=Min{μ(c)}为G中所有圈的平均值的最小值。现在的目标是:在给定了一个图G=(V,E)以及w:E→R之后,请求出G中所有圈c的平均值的最小值μ*(c)=Min{μ(c)}。

【输入】

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

【输出】

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

【输入样例】

4 5

1 2 5

2 3 5

3 1 5

2 4 3

4 1 3

【输出样例】

3.66666667

【数据范围】

20%的数据:n<=100,m<=1000;

50%的数据:n<=1000,m<=5000;

100%的数据:n<=3000,m<=10000;

100%的数据:|wij|<=10^7。

【题解】

典型的分数规划中的最小密度环问题,我们二分一个答案ans,假如答案偏大,则满足以下条件:


答案偏小时类似,所以我们可以用二分值更新每条边,再用SPFA判断是否有负环。如果有,说明答案可以更小,那就更新二分上界,否则更新二分下界。

【代码】

DFS的SPFA判断负环效率更高_(:зゝ∠)_

http://paste.ubuntu.com/10595521/

评论(1)

© OI技术宅 | Powered by LOFTER