网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[東方S3]藤原妹红
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | mokou.in | 输出文件 | mokou.out |
Problem 3 |
藤原妹红(mokou.cpp/c/pas) |
题目描述 |
在幻想乡,藤原妹红(ふじわらのもこう)是拥有不老不死能力的人类。虽然不喜欢与人们交流,妹红仍然保护着误入迷途竹林村民。由于算得上是幻想乡最强的人类,对于她而言,迷途竹林的单向道路亦可以逆行。在妹红眼中,迷途竹林可以视为一个由N个路口(编号1..N),M条不同长度双向路连接的区域。妹红所在的红之自警队为了方便在迷途竹林中行动,绘制了一张特殊的迷途竹林地图,这张地图上只保留了N-1条道路,这些道路保证了任意两个路口间有且仅有一条路径,并且满足所有保留的道路长度之和最小,我们称这些道路为『自警队道路』。现在妹红打算在其中一个连接有多条『自警队道路』的路口设立根据地,当去掉根据地这个根据地所在路口后,就会出现某些路口间无法通过『自警队道路』相互连通的情况,我们认为这时仍然能够通过『自警队道路』连通的路口属于同一个『区域』。妹红希望最后每个『区域』的『自警队道路』总长尽可能平均,请计算出她应该选择哪一个路口作为根据地。 下例中红色的路口为妹红选择的根据地,实线边表示『自警队道路』,绿色虚线边表示非『自警队道路』,数字表示边权,『自警队道路』中相同颜色的实线边代表属于同一个『区域』:
(尽可能平均即权重最小,设每一块『区域』的路线总长为Length[i],平均路线长度为Avg=SUM{Length[i]}/区域数,权重d=∑( (Length[i]-Avg)^2 ) ) |
输入格式 |
第1行:2个正整数N,M 第2..M+1行:每行2个整数u,v和1个实数len,表示u,v之间存在长度为len的边 |
输出格式 |
第1行:1个整数,最后选择的路口编号,存在多个可选路口时选择编号小的 |
输入样例 |
3 3 3 1 5 3 2 4 1 2 3 |
输出样例 |
2 |
样例解释 |
妹红的『自警队道路』为(1,2)和(2,3)。 只能选择2作为根据地,产生的两个区域Length[i]分别为3和4。 所以方差为:(4-3.5)^2 + (3-3.5)^2 = 0.5 |
数据范围 |
对于60%的数据:3 ≤ N ≤ 2,000,N-1 ≤ M ≤ 50,000 对于100%的数据:3 ≤ N ≤ 40,000,N-1 ≤ M ≤ 200,000 对于100%的数据:0 < len ≤ 100,000,000 |
注意 |
保证不存在相同距离的线路,两个路口间可能出现多条路径,且任意点对间至少存在一条路径。 |