[RQNOJ 184]洞窟探索

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 hole.in 输出文件 hole.out
题目背景:
LSZ小朋友组织了一支天文爱好队,他们这次要去探索一个洞窟(天文爱好者怎么探索洞窟?!?),因为据说那里是一个神秘的地方,是地球上最容易捕捉到来自宇宙信息的场所。小朋友带领他的天文爱好队以及许多先进设备来到了洞窟……
题目描述:
洞窟由许许多多的洞穴和通道组成,且任意两个洞穴间有且只有一条路经,每条路经的长度不一定相同。从入口可以进入 1号洞穴,且1号洞穴是唯一与入口相连的洞穴。由于设备有限,小朋友只能在某些洞穴设置他的设备(一个洞穴设一个就足够了)。为了防止迷路,天文爱好队的成员一致决定,每到一个洞窟,就在这里设置一个设备,并留一人看守。
这些设备工作时,任意两个设备间需要通信。通信耗费的时间与这两个洞穴之间的距离有关(指通过通道连接的距离,非两点间距离)。如果有 m个设备,那么共有m*(m-1)/2条路经连接任意两个不同的设备,现在小朋友想知道,选择哪些洞穴,可以使得这些路径的平均长度最小。
平均长度即∑ dist(i,j)/sum,dist(i,j)与dist(j,i)两者只算其中一者(即每两点间的路径长只算一遍),sum:=m*(m-1)/2。
注意:为了使问题简化,我们假设任何一个洞穴最多与另外三个洞穴直接有通道相连。 1号洞穴最多只与两个洞穴直接有通道相连。
输入:
第一行两个整数 n和m,表示洞穴总数和设备数。
以下 n-1行,每行3个整数x y 和 l,表示一条连接x 和 y 洞穴的通道,长度为l。
输出:
仅一行,一个数:表示最小的平均长度。(保留到小数点后 2位)
输入样例:
4 3
1 2 1
1 3 2
2 4 1
输出样例:
1.33
数据规模:
n<=1500,m<=1000,m<=n
保证每条通道的长度为正,且运算过程中不会有超过 longint的情况(在算法正确时)
样例解释:
选择 1、2、4号洞穴,总路径长1+1+2=4,平均长度:4/3=1.33