PKU Judge Online 3723 Conscription

■3723 Conscription

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code

view plainprint?

1. package p3723;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. // AC  
12. public class Main{  
13.   
14.     Scanner sc=new Scanner(System.in);  
15.   
16.     int INF=1<<28;  
17.     double EPS=1e-9;  
18.   
19.     int[] p, rank;  
20.   
21.     void run(){  
22.         int t=Integer.parseInt(sc.next());  
23.         for(int k=0; k<t; k++){  
24.             int n=Integer.parseInt(sc.next());// girl  
25.             int m=Integer.parseInt(sc.next());// boy  
26.             int r=Integer.parseInt(sc.next());  
27.             E[] es=new E[r];  
28.             for(int i=0; i<r; i++){  
29.                 int x=Integer.parseInt(sc.next());  
30.                 int y=Integer.parseInt(sc.next())+n;  
31.                 int d=Integer.parseInt(sc.next());  
32.                 es[i]=new E(x, y, d);  
33.             }  
34.             Arrays.sort(es, new Comparator<E>(){  
35.                 public int compare(E e1, E e2){  
36.                     return e2.d-e1.d;  
37.                 }  
38.             });  
39.   
40.             p=new int[n+m];  
41.             rank=new int[n+m];  
42.             for(int i=0; i<n+m; i++)  
43.                 p[i]=i;  
44.             int sumD=0;  
45.             for(E e : es){  
46.                 // println(e.d+"");  
47.                 if(find(e.x)!=find(e.y)){  
48.                     sumD+=e.d;  
49.                     union(e.x, e.y);  
50.                 }  
51.             }  
52.             int ans=10000*(n+m)-sumD;  
53.             println(""+ans);  
54.         }  
55.     }  
56.   
57.     void union(int x, int y){  
58.         x=find(x);  
59.         y=find(y);  
60.         if(rank[x]<rank[y]){  
61.             p[x]=y;  
62.         }else{  
63.             p[y]=x;  
64.             if(rank[x]==rank[y]){  
65.                 rank[x]++;  
66.             }  
67.         }  
68.     }  
69.   
70.     int find(int x){  
71.         if(p[x]!=x)  
72.             p[x]=find(p[x]);  
73.         return p[x];  
74.     }  
75.   
76.     void print(String s){  
77.         System.out.print(s);  
78.     }  
79.   
80.     void println(String s){  
81.         System.out.println(s);  
82.     }  
83.   
84.     public static void main(String[] args){  
85.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
86.         new Main().run();  
87.     }  
88.   
89.     class E{  
90.         int x, y;  
91.         int d;  
92.   
93.         E(int x, int y, int d){  
94.             this.x=x;  
95.             this.y=y;  
96.             this.d=d;  
97.         }  
98.     }  
99. }  

package p3723;

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

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

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

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

    int[] p, rank;

    void run(){
        int t=Integer.parseInt(sc.next());
        for(int k=0; k<t; k++){
            int n=Integer.parseInt(sc.next());// girl
            int m=Integer.parseInt(sc.next());// boy
            int r=Integer.parseInt(sc.next());
            E[] es=new E[r];
            for(int i=0; i<r; i++){
                int x=Integer.parseInt(sc.next());
                int y=Integer.parseInt(sc.next())+n;
                int d=Integer.parseInt(sc.next());
                es[i]=new E(x, y, d);
            }
            Arrays.sort(es, new Comparator<E>(){
                public int compare(E e1, E e2){
                    return e2.d-e1.d;
                }
            });

            p=new int[n+m];
            rank=new int[n+m];
            for(int i=0; i<n+m; i++)
                p[i]=i;
            int sumD=0;
            for(E e : es){
                // println(e.d+"");
                if(find(e.x)!=find(e.y)){
                    sumD+=e.d;
                    union(e.x, e.y);
                }
            }
            int ans=10000*(n+m)-sumD;
            println(""+ans);
        }
    }

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

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

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

    class E{
        int x, y;
        int d;

        E(int x, int y, int d){
            this.x=x;
            this.y=y;
            this.d=d;
        }
    }
}