「AOJ1121～1130」の編集履歴（バックアップ）一覧に戻る

AOJ1121～1130 - (2012/07/14 (土) 20:02:28) のソース

*1127　Building a Space Station
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1127
宇宙空間に浮かんでいるｎ個(１００個)以内の球状のユニットを最小の長さの通路でつなぐ問題。
ユニットのデータは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);
	}
 }