正因为生来什么都没有,因此我们能拥有一切。(o゚▽゚)o

  • 微信公众号
  • YTU.1012: A MST Problem

    jingyile·2018-11-10·157 次阅读

    题目描述

    It is just a mining spanning tree ( 最小生成树 ) problem, what makes you a little difficult is that you are in a 3D space.

    输入

    The first line of the input contains the number of test cases in the file. And t he first line of each case
    contains one integer numbers n(0<n<30) specifying the number of the point . The n next n line s, each line
    contain s Three Integer Numbers xi,yi and zi, indicating the position of point i.

    输出

    For each test case, output a line with the answer, which should accurately rounded to two decimals .

    样例输入

     

    样例输出

     

    分析:3D空间上的最小生成树问题,

    一个三维坐标点可以看成最小生成树的一个节点,那么三维空间里的点与点之间的距离就可以看成这两个节点间边的权重。

    可以用结构体保存各个点的坐标x,y,z;

    因为好久没写过prim算法,遇到点问题,用kruskal提交AC。

    kruskal算法:

    prim算法:

     

     

     


    正因为生来什么都没有,因此我们能拥有一切。(o゚▽゚)o

    
    
    查看评论

    Post a new comment

    Post a new comment
    欢迎回来 , [ 修改 ]




    加载中……