[BOJ] 2126 지진 (JAVA)

https://www.acmicpc.net/problem/2126

2126번: 지진

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N, M;
    static double F, mid, left, right;
    static int[] parent;
    static ArrayList<Edge> list = new ArrayList<>();

    public static void main(String[] args) throws Exception {

        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken()); // 정점 수
        M = Integer.parseInt(st.nextToken()); // 간선 수
        F = right = Integer.parseInt(st.nextToken()); // 복원 비용
        parent = new int[N + 1];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            double c = Double.parseDouble(st.nextToken());
            double t = Double.parseDouble(st.nextToken());
            list.add(new Edge(from, to, c, t));
        }

        for (int i = 0; i < 100; i++) {
            make();

            mid = (left + right) / 2;

            if (kruskal(mid)) left = mid;
            else right = mid;
        }

        System.out.printf("%.4f", mid < 0 ? 0.0000 : mid);

    }

    static boolean kruskal(double mid) {
        Collections.sort(list, (o1, o2) -> (o1.c + o1.t * mid) < (o2.c + o2.t * mid) ? -1 : (o1.c + o1.t * mid) == (o2.c + o2.t * mid) ? 0 : 1);

        double sum = 0;
        int tempCnt = 1;

        for (Edge e : list) {
            if (union(e.from, e.to)) {
                sum += (e.c + e.t * mid);
                if (++tempCnt == N) break;
            }
        }

        return sum <= F;
    }

    static boolean union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) return false;

        if (a < b) parent[b] = a;
        else parent[a] = b;
        return true;
    }

    static int find(int a) {
        if (parent[a] == a) return a;
        return parent[a] = find(parent[a]);
    }

    static void make() {
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
    }

    static class Edge {
        int from, to;
        double c, t;

        public Edge (int from, int to, double c, double t) {
            this.from = from;
            this.to = to;
            this.c = c;
            this.t = t;
        }
    }
	
}