Building a Space Station(bfs)

http://poj.org/problem?id=2031

题意：给出n个球的圆心坐标x,y,z, 半径r，若任意两球不相交，则在两球间建桥。问需建桥的最短距离是多少。

思路：建图,以两球间相差的距离为权值，然后求最小生成树。

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 const int inf=1<<28;
 5 const double eps=1e-8;
 6 const int maxn=120;
 7 double sum,Map[maxn][maxn],dis[maxn];
 8 int vis[maxn];
 9 struct point
10 {
11     double x,y,z,r;
12 };
13 void prim(int n)
14 {
15     for (int i = 1; i <= n; i++)
16         dis[i]=inf;
17     dis[1]=0;
18     sum=0;
19     for (int i = 1; i <= n; i++)
20     {
21         double Min=inf;
22         int pos=0;
23         for (int j = 1; j <= n; j++)
24         {
25             if (!vis[j]&&dis[j] < Min)
26             {
27                 Min = dis[j];
28                 pos = j;
29             }
30         }
31         if (Min==inf)
32             return;
33         vis[pos] = 1;
34         sum+=Min;
35         for (int j = 1; j <= n; j++)
36         {
37             if (!vis[j]&&dis[j] > Map[pos][j])
38                 dis[j] = Map[pos][j];
39         }
40     }
41 }
42 void init()
43 {
44     sum = 0;
45     memset(vis,0,sizeof(vis));
46     memset(Map,0,sizeof(Map));
47 }
48 double dist(point &a,point &b)
49 {
50     return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
51 }
52 int main()
53 {
54     int n;
55     while(~scanf("%d",&n)&&n)
56     {
57         point a[120];
58         init();
59         for (int i = 1; i <= n; i++)
60         {
61             scanf("%lf%lf%lf%lf",&a[i].x,&a[i].y,&a[i].z,&a[i].r);
62         }
63         for (int i = 1; i <= n; i++)
64         {
65             for (int j = 1; j <= n; j++)
66             {
67                 double d = sqrt(dist(a[i],a[j]));
68                 if (d-(a[i].r+a[j].r)>eps)
69                     Map[i][j] = d-a[i].r-a[j].r;
70                 else
71                     Map[i][j] = 0;
72             }
73         }
74         prim(n);
75         printf("%.3f
",sum);
76     }
77     return 0;
78 }

View Code