1127 Building a Space Station

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1127
宇宙空間に浮かんでいるn個(100個)以内の球状のユニットを最小の長さの通路でつなぐ問題。
ユニットのデータはx,y,z,rで与えらる座標と半径である。
球同士が共通部分を持つ場合長さ0の辺でつなぐことが出来る。
長さをグラフに翻訳したら後はプリム法で解くだけです。
昔プリム法を知らずに自力で同じ手法を考案して(車輪の再発明)して似た問題を解いたことがあるので感慨深い問題です。



#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string.h>
#include<queue> 
struct E{
int no;
double cost;
bool operator<(const E& e)const{
	return cost>e.cost;
}
};
void calc(int n){
double xs[101],ys[101],zs[101],rs[101],len,ans=0;
double lens[101][101];
double mymax=1000000000;
for(int i=0;i<n;i++){
	scanf("%lf %lf %lf %lf",&xs[i],&ys[i],&zs[i],&rs[i]);
	lens[i][i]=mymax;
	for(int j=0;j<i;j++){
		len=sqrt(pow(xs[i]-xs[j],2)+pow(ys[i]-ys[j],2)+pow(zs[i]-zs[j],2))-rs[i]-rs[j];
		if(len<=0)len=0;
		lens[i][j]=lens[j][i]=len;
	}
}
bool conOKs[101];
memset(conOKs,false,sizeof(conOKs));
E e1;
int no;
e1.no=0;
e1.cost=0;
std::priority_queue<E> qu;
qu.push(e1);
while(!qu.empty()){
	e1=qu.top();
	qu.pop();
	no=e1.no;
	if(conOKs[no]==true)continue;
	conOKs[no]=true;
	ans+=e1.cost;
	for(int i=0;i<n;i++){
		if(i==no||conOKs[i]==true)continue;
		e1.no=i;
		e1.cost=lens[no][i];
		qu.push(e1);
	}
}
printf("%.3lf\n",ans);
}
int main(){
int n;
while(1){
	scanf("%d",&n);
	if(n==0)break;
	calc(n);
}
}

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2012年07月14日 20:02