stdKonjac's Blog

 要做到不可替代,就要与众不同。

【修建道路】

题目描述

Farmer John最近得到了一些新的农场,他想新修一些道路使得他的所有农场可以经过原有的或是新修的道路互达(也就是说,从任一个农场都可以经过一些首尾相连道路到达剩下的所有农场)。有些农场之间原本就有道路相连。

所有 N(1<=N<=1,000) 个农场(用 1..N 顺次编号)在地图上都表示为坐标为(Xi,Yi)的点(0<=Xi<=1,000,000;0<=Yi<=1,000,000),两个农场间道路的长度自然就是代表它们的点之间的距离。

现在 Farmer John 也告诉了你农场间原有的 M(1<=M<=1,000)条路分别连接了哪两个农场,他希望你计算一下,为了使得所有农场连通,他所需建造道路的最小总长是多少。

输入格式

第 1 行:2 个用空格隔开的整数:N 和 M
第 2..N+1 行:第 i+1 行为 2 个用空格隔开的整数:Xi、Yi
第 N+2..N+M+2 行:每行用 2 个以空格隔开的整数 i、j 描述了一条已有的道路,这条道路连接了农场 i 和农场 j 。

输出格式

输出使所有农场连通所需建设道路的最小总长,保留 2 位小数,不必做任何额外的取整操作。为了避免精度误差,计算农场间距离及答案时,请使用 64 位实型变量。

样例数据 1

输入

4 1
1 1
3 1
2 3
4 3
1 4

输出

4.00

裸MST,只是double这个东西一不注意就会CE……还有输出的时候用%.2f不要用%.2lf !!!总之先把已经有连边的点做个并查集,然后把所有点的距离计算出来,之后裸MST就行了。
下面是代码:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.