Aizu Online Judge 0072 Carden Lantern

■0072 Carden Lantern

ただの最小全域木．木を構成しながら，(コスト/100-1)を灯篭の数としてカウントアップしていく．

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%lt;%lt;28;  
14.  double EPS=1e-9;  
15.   
16.  int n, m;  
17.  int[][] w;  
18.   
19.  void run(){  
20.   sc.useDelimiter("[,]|(\\s)+");  
21.   for(; sc.hasNext();){  
22.    n=sc.nextInt();  
23.    if(n==0){  
24.     break;  
25.    }  
26.    m=sc.nextInt();  
27.    w=new int[n][n];  
28.    for(int i=0; i%lt;n; i++){  
29.     Arrays.fill(w[i], -1);  
30.    }  
31.    for(int i=0; i%lt;m; i++){  
32.     int a=sc.nextInt();  
33.     int b=sc.nextInt();  
34.     int c=sc.nextInt()/100;  
35.     w[a][b]=w[b][a]=c;  
36.    }  
37.    solve();  
38.   }  
39.  }  
40.   
41.  // w[i][j]=w[j][i]  
42.  // w[i][j]=-1 -> E(i, j) not exist  
43.  void solve(){  
44.   init();  
45.   LinkedList%lt;E> list=new LinkedList%lt;E>();  
46.   
47.   for(int j=0; j%lt;n-1; j++)  
48.    for(int i=j+1; i%lt;n; i++)  
49.     if(w[j][i]!=-1)  
50.      list.add(new E(j, i, w[j][i]));  
51.   
52.   E[] es=list.toArray(new E[0]);  
53.   Arrays.sort(es, new Comparator%lt;E>(){  
54.    @Override  
55.    public int compare(E e1, E e2){  
56.     return e1.w-e2.w;  
57.    }  
58.   });  
59.   
60.   list.clear();  
61.   int ans=0;  
62.   for(E e : es){  
63.    if(find(e.v1)!=find(e.v2)){  
64.     union(e.v1, e.v2);  
65.     ans+=e.w-1;  
66.     list.add(e);  
67.    }  
68.   }  
69.   println(""+ans);  
70.  }  
71.   
72.  int[] p, rank;  
73.   
74.  void init(){  
75.   p=new int[n];  
76.   rank=new int[n];  
77.   for(int i=0; i%lt;n; i++){  
78.    p[i]=i;  
79.    rank[i]=0;  
80.   }  
81.  }  
82.   
83.  int find(int x){  
84.   if(p[x]==x)  
85.    return x;  
86.   else  
87.    return p[x]=find(p[x]);  
88.  }  
89.   
90.  void union(int x, int y){  
91.   x=find(x);  
92.   y=find(y);  
93.   if(rank[x]>rank[y]){  
94.    p[y]=x;  
95.   }else{  
96.    p[x]=y;  
97.    if(rank[x]==rank[y])  
98.     rank[y]++;  
99.   }  
100.  }  
101.   
102.  class E{  
103.   int v1, v2, w;  
104.   
105.   E(int v1, int v2, int w){  
106.    this.v1=v1;  
107.    this.v2=v2;  
108.    this.w=w;  
109.   }  
110.  }  
111.   
112.  void debug(Object... os){  
113.   System.err.println(Arrays.deepToString(os));  
114.  }  
115.   
116.  void print(String s){  
117.   System.out.print(s);  
118.  }  
119.   
120.  void println(String s){  
121.   System.out.println(s);  
122.  }  
123.   
124.  public static void main(String[] args){  
125.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
126.   new Main().run();  
127.  }  
128. }  

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%lt;%lt;28;
 double EPS=1e-9;

 int n, m;
 int[][] w;

 void run(){
  sc.useDelimiter("[,]|(\\s)+");
  for(; sc.hasNext();){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   m=sc.nextInt();
   w=new int[n][n];
   for(int i=0; i%lt;n; i++){
    Arrays.fill(w[i], -1);
   }
   for(int i=0; i%lt;m; i++){
    int a=sc.nextInt();
    int b=sc.nextInt();
    int c=sc.nextInt()/100;
    w[a][b]=w[b][a]=c;
   }
   solve();
  }
 }

 // w[i][j]=w[j][i]
 // w[i][j]=-1 -> E(i, j) not exist
 void solve(){
  init();
  LinkedList%lt;E> list=new LinkedList%lt;E>();

  for(int j=0; j%lt;n-1; j++)
   for(int i=j+1; i%lt;n; i++)
    if(w[j][i]!=-1)
     list.add(new E(j, i, w[j][i]));

  E[] es=list.toArray(new E[0]);
  Arrays.sort(es, new Comparator%lt;E>(){
   @Override
   public int compare(E e1, E e2){
    return e1.w-e2.w;
   }
  });

  list.clear();
  int ans=0;
  for(E e : es){
   if(find(e.v1)!=find(e.v2)){
    union(e.v1, e.v2);
    ans+=e.w-1;
    list.add(e);
   }
  }
  println(""+ans);
 }

 int[] p, rank;

 void init(){
  p=new int[n];
  rank=new int[n];
  for(int i=0; i%lt;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]++;
  }
 }

 class E{
  int v1, v2, w;

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

 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();
 }
}