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

2016年7月14日 0 作者 CrazyKK

poj 2031

 

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

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