poj 2031 Building a Space Station (最小生成树)

poj 2031

 

题意:三维空间中n个球要相连。。。通路的代价是距离。。。如果球相交(切)或者包含那么不用建通路就能联系。。。问联系所有球的最小代价。。。

思路:裸的最小生成树。。。。先预处理球和球表面的距离。。。距离是负数的处理成0.。。然后mst搞之。。。不算CE的话是1A….

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz