【NOIP模拟赛】警察叔叔就是这个人!

2014年10月18日1,4280

题目背景

十个地方十人十色

全部都是猥琐大叔

这里也是那里也是

行踪可疑

现如今hentai横行,警察叔叔们不得不采取特♂殊手段惩戒这些家伙

题目描述

魅力之都是一个有N个路口,M条双向道路连接的城市。警察叔叔绘制了一张特殊的地图,在地图上只保留了N-1条道路,我们称这些道路为【特殊道路】,要保证任意两个路口间有且仅有一条路径,且满足所有保留的道路长度之和最小。

现在要在其中一个连接有多条【特殊道路】的路口设立【根据地】,去掉【根据地】所在路口后,就会出现某些路口间无法通过【特殊道路】相互连通的情况,我们认为这时仍然能够通过【特殊道路】连通的路口属于同一个【区域】。警察叔叔希望最后每个【区域】的【特殊道路】总长尽可能平均。警察叔叔找到了hzwer,但是hzwer是个无向图和有向图都无法区分的蒟蒻,请你帮他计算出应该选择哪一个路口作为【根据地】。

(尽可能平均即权值最小,设每一块【区域】的路线总长为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个整数,最后选择的路口编号(存在多个可选路口时选择编号小的)

样例数据 1

输入

3 3
3 1 5
3 2 4
1 2 3

输出

2

样例数据 2

输入

3 3
2 1 825.7291
3 2 397.4120
1 3 633.1370

输出

3

备注

对于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

保证不存在相同距离的线路,两个路口间可能出现多条路径,且任意点对间至少存在一条路径

题解

题目大意

给定一个无向有权图,首先一个最小生成树 MST,从 MST 中选取一个度数大于 1 的点 作为根 K,使每颗子树及该子树到根的边权之和方差最小。输出 K 和最小方差的值。

考察算法最小生成树 树的遍历

算法1

首先毫无疑问的需要用到求最小生成树的算法,我们考虑使用 Kruskal 算法或是Prim 算法。求出最小生成树以后,依次枚举每一个点作为根进行遍历,取出其中的最小方差即可。

时间复杂度:O(MlogM+N^2)

期望得分:60

算法2

由于后 40%的数据 N 比较大,所以只能通过 Kruskal 算法求出最小生成树,接下来任选一个点作为根,进行一次遍历。记录 w[i]表示以 i 点作为根的子树的边权之和。 然后依次枚举每一个点 i,该点的子树权值可以直接求出,而以它父亲作为根的子树需要特殊处理。这颗特殊子树的权值为最小生成树总权值减去该点权值 w[i]。然后计算出方差,最后选取所有点当中最小方差的那个点即可。

时间复杂度:O(MlogM+N)

期望得分:100

本题来自东方系列模拟赛stage3

真的不是我懒得写代码。。

我的代码被我手贱删了,那我做个搬运工好了。。。

暴力:

正解