• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ2031 – Building a Space Station

    ACM-POJ EXP 118阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    就是给出三维坐标系上的一些球的球心坐标和其半径,搭建通路,使得他们能够相互连通。如果两个球有重叠的部分则算为已连通,无需再搭桥。求搭建通路的最小费用(费用就是边权,就是两个球面之间的距离)。

    解题思路

    不要被三维吓到了,其实就是图论的最小生成树问题

    球心坐标和半径是用来求 两点之间的边权 的,求出边权后,把球看做点,用邻接矩阵存储这个无向图,再求最小生成树,非常简单的水题。

    把球A和球B看做无向图图的两个结点,那么

    边权 = AB球面距离 = A球心到B球心的距离 – A球半径 – B球半径

    边权直接用上面的公式求,接下来再用Prim就能完美AC了

    注意若边权<=0,说明两球接触,即已连通,此时边权为0

    转载请注明:EXP 技术分享博客 » POJ2031 – Building a Space Station

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址