PKU Judge Online 3723 Conscription

■3723 Conscription

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

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

□Code

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