本题为最小生成树裸题,直接套模版按题意修改就行了
本题与P1991相同,但要注意本题有多组数据,而P1991只有一组
题意:
给出n个节点的坐标,S个卫星,每个节点相互之间连通且边权为两点间距离,求这个图的最小生成树,输出最小生成树中第S-1长的边的边权,保留两位小数。
注意:S个卫星相当于S-1条边权值为0的边。
这题我是用$Prim$做的,由于看到大家发的都是Kruskal的题解,所以我就补充一篇$Prim$的。
记得存边权的变量要用double
AC代码(只能借鉴,不能抄哦):
1 |
|
本题似乎可以在建图时把卫星作为节点处理,用于替换普通节点,不过要设置两卫星间边权为0。