题目链接：
https://vjudge.net/problem/POJ-2031
题目大意：
就是给出三维坐标系上的一些球的球心坐标和其半径，搭建通路，使得他们能够相互连通。如果两个球有重叠的部分则算为已连通，无需再搭桥。求搭建通路的最小费用（费用就是边权，就是两个球面之间的距离）。
思路：
MST模板+空间距离计算
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #include<stack> 8 #include<map> 9 #include<sstream> 10 using namespace std; 11 typedef long long ll; 12 const int maxn = 2e2 + 10; 13 const int INF = 1 << 30; 14 int dir[4][2] = {1,0,0,1,-1,0,0,-1}; 15 int T, n, m, x; 16 struct node 17 { 18 double x, y, z, r; 19 node(){} 20 node(double x, double y, double z, double r):x(x), y(y), z(z), r(r){} 21 }; 22 node a[maxn]; 23 double Map[maxn][maxn];//存图 24 double lowcost[maxn], mst[maxn]; 25 void prim(int u)//最小生成树起点 26 { 27 double sum_mst = 0;//最小生成树权值 28 for(int i = 1; i <= n; i++)//初始化两个数组 29 { 30 lowcost[i] = Map[u][i]; 31 mst[i] = u; 32 } 33 mst[u] = -1;//设置成-1表示已经加入mst 34 for(int i = 1; i <= n; i++) 35 { 36 double minn = INF; 37 int v = -1; 38 //在lowcost数组中寻找未加入mst的最小值 39 for(int j = 1; j <= n; j++) 40 { 41 if(mst[j] != -1 && lowcost[j] < minn) 42 { 43 v = j; 44 minn = lowcost[j]; 45 } 46 } 47 if(v != -1)//v=-1表示未找到最小的边, 48 {//v表示当前距离mst最短的点 49 //printf("%d %d %d ", mst[v], v, lowcost[v]);//输出路径 50 mst[v] = -1; 51 sum_mst += lowcost[v]; 52 for(int j = 1; j <= n; j++)//更新最短边 53 { 54 if(mst[j] != -1 && lowcost[j] > Map[v][j]) 55 { 56 lowcost[j] = Map[v][j]; 57 mst[j] = v; 58 } 59 } 60 } 61 } 62 //printf("weight of mst is %d ", sum_mst); 63 printf("%.3f ", sum_mst); 64 } 65 double f(int i, int j) 66 { 67 double l; 68 l = sqrt((a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y) + (a[i].z - a[j].z) * (a[i].z - a[j].z)); 69 l = l - a[i].r - a[j].r; 70 if(l <= 0)return 0; 71 else return l; 72 } 73 int main() 74 { 75 while(cin >> n && n) 76 { 77 for(int i = 1; i <= n; i++)cin >> a[i].x >> a[i].y >> a[i].z >> a[i].r; 78 for(int i = 1; i <= n; i++) 79 { 80 for(int j = i; j <= n; j++) 81 { 82 Map[i][j] = Map[j][i] = f(i, j); 83 } 84 } 85 prim(1); 86 } 87 return 0; 88 }