1127-Building a Space Station
問題概要
xyz空間に球がいくつかある。
その球全てを結ぶ通路を作るのに必要な通路の流さの最小値を求めよ
考え方
ただの最小全域木の問題。
実装(C++)
Weight kruskal(const Graph &G){ int V=G.size(); Weight res=0;UnionFind uf(V);Graph n(V);Edge t; priority_queue<Edge,vector<Edge>,greater<Edge> > que; for(int i=0;i<(int)G.size();i++)for(int j=0;j<(int)G[i].size();j++)if(G[i][j].src<G[i][j].dst)que.push(G[i][j]); while(!que.empty()){ t=que.top();que.pop(); if(!uf.same(t.dst,t.src)){ uf.unite(t.dst,t.src);res+=t.cost; n[t.src].push_back(t); } } return res; } struct Point{ double x,y,z,r; }; double dist(const Point &a,const Point &b){ double t=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z); t=sqrt(t); t-=a.r+b.r; if(t<=0)t=0; return t; } int main() { int n; for(;cin>>n,n;){ vector<Point> pts(n); Graph G(n); for(int i=0;i<n;i++){ cin>>pts[i].x>>pts[i].y>>pts[i].z>>pts[i].r; } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ G[i].push_back(Edge(i,j,dist(pts[i],pts[j]))); } } printf("%.3f\n",kruskal(G)); } return 0; }