Aizu Online Judge 0180 Stellar Performance of the Debunkey Family

■0180 Stellar Performance of the Debunkey Family

最小全域木．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int n, m;  
17.  LinkedList<E> list;  
18.   
19.  void run(){  
20.   for(;;){  
21.    n=sc.nextInt();  
22.    m=sc.nextInt();  
23.    if((n|m)==0){  
24.     break;  
25.    }  
26.    list=new LinkedList<E>();  
27.    for(int i=0; i<m; i++){  
28.     int a=sc.nextInt();  
29.     int b=sc.nextInt();  
30.     int cost=sc.nextInt();  
31.     list.add(new E(a, b, cost));  
32.    }  
33.    solve();  
34.   }  
35.  }  
36.   
37.  void solve(){  
38.   E[] es=list.toArray(new E[0]);  
39.   Arrays.sort(es);  
40.   init();  
41.   int wt=0;  
42.   for(E e : es){  
43.    if(find(e.v1)!=find(e.v2)){  
44.     union(e.v1, e.v2);  
45.     wt+=e.w;  
46.    }  
47.   }  
48.   println(""+wt);  
49.  }  
50.   
51.  class E implements Comparable<E>{  
52.   int v1, v2, w;  
53.   
54.   E(int v1, int v2, int w){  
55.    this.v1=v1;  
56.    this.v2=v2;  
57.    this.w=w;  
58.   }  
59.   
60.   @Override  
61.   public int compareTo(E e){  
62.    return w-e.w;  
63.   }  
64.  }  
65.   
66.  int[] p, rank;  
67.   
68.  void init(){  
69.   p=new int[n];  
70.   rank=new int[n];  
71.   for(int i=0; i<n; i++){  
72.    p[i]=i;  
73.    rank[i]=0;  
74.   }  
75.  }  
76.   
77.  int find(int x){  
78.   if(p[x]==x)  
79.    return x;  
80.   else  
81.    return p[x]=find(p[x]);  
82.  }  
83.   
84.  void union(int x, int y){  
85.   x=find(x);  
86.   y=find(y);  
87.   if(rank[x]>rank[y]){  
88.    p[y]=x;  
89.   }else{  
90.    p[x]=y;  
91.    if(rank[x]==rank[y])  
92.     rank[y]++;  
93.   }  
94.  }  
95.   
96.  void debug(Object... os){  
97.   System.err.println(Arrays.deepToString(os));  
98.  }  
99.   
100.  void print(String s){  
101.   System.out.print(s);  
102.  }  
103.   
104.  void println(String s){  
105.   System.out.println(s);  
106.  }  
107.   
108.  public static void main(String[] args){  
109.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
110.   new Main().run();  
111.  }  
112. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, m;
 LinkedList<E> list;

 void run(){
  for(;;){
   n=sc.nextInt();
   m=sc.nextInt();
   if((n|m)==0){
    break;
   }
   list=new LinkedList<E>();
   for(int i=0; i<m; i++){
    int a=sc.nextInt();
    int b=sc.nextInt();
    int cost=sc.nextInt();
    list.add(new E(a, b, cost));
   }
   solve();
  }
 }

 void solve(){
  E[] es=list.toArray(new E[0]);
  Arrays.sort(es);
  init();
  int wt=0;
  for(E e : es){
   if(find(e.v1)!=find(e.v2)){
    union(e.v1, e.v2);
    wt+=e.w;
   }
  }
  println(""+wt);
 }

 class E implements Comparable<E>{
  int v1, v2, w;

  E(int v1, int v2, int w){
   this.v1=v1;
   this.v2=v2;
   this.w=w;
  }

  @Override
  public int compareTo(E e){
   return w-e.w;
  }
 }

 int[] p, rank;

 void init(){
  p=new int[n];
  rank=new int[n];
  for(int i=0; i<n; i++){
   p[i]=i;
   rank[i]=0;
  }
 }

 int find(int x){
  if(p[x]==x)
   return x;
  else
   return p[x]=find(p[x]);
 }

 void union(int x, int y){
  x=find(x);
  y=find(y);
  if(rank[x]>rank[y]){
   p[y]=x;
  }else{
   p[x]=y;
   if(rank[x]==rank[y])
    rank[y]++;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}