「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
宇宙空間に浮かんでいる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);
}
}
*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);
}
}