2031 Building a Space Station

「2031 Building a Space Station」の編集履歴（バックアップ）一覧はこちら

「2031 Building a Space Station」(2006/04/17 (月) 01:58:48) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**2031 Building a Space Station
**問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=2031
**解答方針
最小全域木．今回はKruskalのアルゴリズムで解いた．
**解答例
 import java.io.*;
 import java.util.*;
 import java.text.*;
 
 public class Main{
     public static void main(String[] args)throws IOException{
         Scanner sc = new Scanner(System.in);
         DecimalFormat formatter = new DecimalFormat("#0.000");
         int n = sc.nextInt();
         while(n!=0){
             double data[][] = new double[n][4];
             for(int i=0;i<n;i++){
                 data[i][0] = sc.nextDouble();
                 data[i][1] = sc.nextDouble();
                 data[i][2] = sc.nextDouble();
                 data[i][3] = sc.nextDouble();
             }
             
             Solver s = new Solver(n,data);
             double ans = s.solve();
             
             System.out.println(formatter.format(ans));
             
             n = sc.nextInt();
         }
     }
 }
 
 class Solver{
     int size;
     int connected[];//expression of MF-SET
     PriorityQueue<Edge> q;
     Solver(int n,double data[][]){
         size = n;
         connected = new int[size];
         q = new PriorityQueue<Edge>();
         for(int i=0;i<n;i++){
             for(int j=i+1;j<n;j++){
                 double elen = edgeLength(data[i],data[j]);
                 Edge e = new Edge(i,j,elen);
                 q.offer(e);
             }
         }
         for(int i=0;i<n;i++) connected[i] = i;
     }
     
     public double solve(){
         double corlen;
         corlen = 0;
         //Kruskal's algorithm
         while(!q.isEmpty()){
             Edge e = q.poll();
             int i = e.p1;
             int j = e.p2;
             if(connected[i]!=connected[j]){
                 merge(i,j);
                 corlen += e.length;
             }
         }
         return corlen;
     }
     
     //MERGE OF MF-SET
     private void merge(int i,int j){
         int m1 = connected[i];
         int m2 = connected[j];
         for(int k=0;k<size;k++){
             if(connected[k]==m2) connected[k] = m1;
         }
     }
     
     private double edgeLength(double d1[],double d2[]){
         double dx = d1[0]-d2[0];
         double dy = d1[1]-d2[1];
         double dz = d1[2]-d2[2];
         double dist = Math.sqrt(dx*dx+dy*dy+dz*dz);
         double prelen = dist - (d1[3]+d2[3]);
         if(prelen>=0.0) return prelen;
         else return 0.0;
     }
 }
 
 class Edge implements Comparable<Edge>{
     int p1;
     int p2;
     double length;
     Edge(int i,int j,double l){
         p1 = i;
         p2 = j;
         length = l;
     }
     public int compareTo(Edge e){
         if(length>e.length) return 1;
         else if(length==e.length) return 0;
         else return -1;
     }
 }