http://poj.org/problem?id=2031
题意
给出三维坐标系下的n个球体,求把它们联通的最小代价。
分析
最小生成树加上一点计算几何。建图,若两球体原本有接触,则边权为0;否则边权为它们球心的距离-两者半径之和。这样来跑Prim就ok了。注意精度。
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
#define rep(i,e) for(int i=0;i<(e);i++)
#define rep1(i,e) for(int i=1;i<=(e);i++)
#define repx(i,x,e) for(int i=(x);i<=(e);i++)
#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define mset(var,val) memset(var,val,sizeof(var))
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define pd(a) printf("%d\n",a)
#define scl(a) scanf("%lld",&a)
#define scll(a,b) scanf("%lld%lld",&a,&b)
#define sclll(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define lc idx<<1
#define rc idx<<1|1
#define rson mid+1,r,rc
#define lson l,mid,lc
using namespace std;
typedef long long ll;
template <class T>
void test(T a) {
cout<<a<<endl;
}
template <class T,class T2>
void test(T a,T2 b) {
cout<<a<<" "<<b<<endl;
}
template <class T,class T2,class T3>
void test(T a,T2 b,T3 c) {
cout<<a<<" "<<b<<" "<<c<<endl;
}
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const ll mod = 1e9+;
int T;
void testcase() {
printf("Case %d: ",++T);
}
const int MAXN = 1e5+;
const int MAXM = ;
const double PI = acos(-1.0);
const double eps = 1e-;
struct node{
double x,y,z,r;
}p[];
double dist(node a,node b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}
double g[][],lowc[];
bool vis[];
int main() {
#ifdef LOCAL
freopen("data.in","r",stdin);
#endif // LOCAL
int n;
while(~scd(n)&&n){
for(int i=;i<n;i++){
scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z,&p[i].r);
}
double maxx=0.0;
for(int i=;i<n;i++){
g[i][i]=0.0;
for(int j=i+;j<n;j++){
if(dist(p[i],p[j])-(p[i].r+p[j].r)<=eps){
g[i][j]=g[j][i]=0.0;
}else{
g[i][j]=g[j][i]=dist(p[i],p[j])-(p[i].r+p[j].r);
maxx=max(maxx,g[i][j]);
}
}
}
mset(vis,false);
double ans=;
vis[]=true;
for(int i=;i<n;i++) lowc[i]=g[][i];
for(int i=;i<n;i++){
double minc = maxx;
int p=-;
for(int j=;j<n;j++){
if(!vis[j]&&minc>lowc[j]){
minc=lowc[j];
p=j;
}
}
ans+=minc;
vis[p]=true;
for(int j=;j<n;j++){
if(!vis[j]&&lowc[j]-g[p][j]>eps){
lowc[j]=g[p][j];
}
}
} printf("%.3f\n",ans);
}
return ;
}