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

poj 2031

 

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

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

 

 

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
 
 
/* ***********************************************
Author :111qqz
Created Time :2016年07月14日 星期四 15时44分53秒
File Name :code/poj/2031.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const  int N =105;
int n;
int m;
double a[N][N];
int f[N];
int dblcmp(double d)
{
    return d<-eps?-1:d>eps;
}
void init()
{
    for ( int i = 1 ; i  <= n ; i++) f[i] = i;
}
struct circle
{
    double x,y,z,r;
    double dis(circle b)
    {
        double res = 0 ;
        res = (x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)+(z-b.z)*(z-b.z);
        res = sqrt(res);
        res = res - r - b.r;
        if (dblcmp(res)<0) res = 0 ;
        return res;
    }
    void input()
    {
        scanf("%lf%lf%lf%lf",&x,&y,&z,&r);
    }
}cir[N];
struct Edge
{
    int u,v;
    double w;
    bool operator < (Edge b)const
    {
        return w<b.w;
    }
}edge[N*N/2];
int root ( int x)
{
    if (x!=f[x]) f[x] = root (f[x]);
    return f[x];
}
void merge( int x,int y)
{
    int rx = root (x);
    int ry = root(y);
    if (rx==ry) return;
    f[rx] = ry;
}
int main()
{
#ifndef  ONLINE_JUDGE
    freopen("code/in.txt","r",stdin);
#endif
    while (~scanf("%d",&n))
    {
        if (n==0) break;
        init();
        for ( int i = 1 ;i  <= n ; i++) cir[i].input();
        for ( int i = 1 ; i <= n ; i++)
            for ( int j = 1 ; j <= n ; j++)
                a[i][j]=a[j][i]=cir[i].dis(cir[j]);
        m = 0 ;
        for ( int i = 1 ; i <= n ; i++)
            for ( int j = 1 ; j <= n ; j++)
                if (i<j)
                {
                    m++;
                    edge[m].u = i ;
                    edge[m].v = j;
                    edge[m].w = a[i][j];
                }
        sort(edge+1,edge+m+1);
        double mst = 0 ;
        int cnt = 0 ;
        for ( int i = 1 ; i <= m ; i++)
        {
            int u = edge[i].u;
            int v = edge[i].v;
            double w = edge[i].w;
            if (root(u)==root(v)) continue;
            merge(u,v);
            mst +=w;
            cnt++;
            if (cnt>=n-1) break;
        }
        if (dblcmp(mst)==0)
        {
            puts("0.000");
        }else
        {
            printf("%.3f\n",mst);
        }
    }
#ifndef ONLINE_JUDGE  
    fclose(stdin);
#endif
    return 0;
}
 
 
 
 

作者： CrazyKK

ex-ACMer@hust，stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人！

提醒
wpDiscuz