1. 문제 설명

지진

2. 문제 분석

MST를 통해 주어진 기준에 따라 가장 높은 이득을 얻어내는 값을 구한다. 이때 모든 경우를 탐색하는 게 아니라 이분 탐색을 통해 탐색 경우를 줄일 수 있다.

1. 주어진 간선 복구 비용 및 시간이 주어진다. 시간 당 이득을 gain이라고 하면 간선을 (간선 복구 비용) + (간선 복구 시간 * gain) 기준으로 정렬한다. 오름차순 정렬을 통해 최소 비용 간선부터 꺼내올 수 있다.
2. 시간 당 이득은 0 ~ F로 중 하나로 카운트, 이분 탐색을 통해 가장 높은 이득이 되는 경우를 탐색한다.
3. 매번 MST을 얻기 위해 크루스칼 알고리즘을 반복하므로, parents를 통해 루트 집합을 초기화 + 간선 정보 정렬을 체크.

3. 나의 풀이

import Foundation

let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M, F) = (input[0], input[1], input[2])
var edges = [(Int, Int, Int, Int)]()
for _ in 0..<M {
    let edge = readLine()!.split(separator: " ").map{Int(String($0))!}
    edges.append((edge[0], edge[1], edge[2], edge[3]))
}
var left = 0.0
var right = Double(F)

func find(node:Int) -> Int {
    if parents[node] == node {
        return node
    } else {
        parents[node] = find(node:parents[node])
        return parents[node]
    }
}

func union(node1:Int, node2:Int) -> Bool {
    let root1 = find(node: node1)
    let root2 = find(node: node2)
    
    if root1 == root2 {
        return false
    } else {
        parents[root2] = root1
        return true
    }
}

func Kruskal(mid:Double) -> Bool {
    func edgeSort(num1: (Int, Int, Int, Int), num2: (Int, Int, Int, Int)) -> Bool {
        return (Double(num1.2) + Double(num1.3) * mid) < (Double(num2.2) + Double(num2.3) * mid)
    }
    edges.sort(by: edgeSort)
    var total = 0.0
    var edgeCnt = 0
    for edge in edges {
        let node1 = edge.0
        let node2 = edge.1
        let cost = edge.2
        let time = edge.3
        if union(node1: node1, node2: node2) == true {
            total += (Double(cost) + Double(time) * mid)
            edgeCnt += 1
            if edgeCnt == N-1 {
                break
            }
        }
    }
    if total <= Double(F) {
        return true
    } else {
        return false
    }
}

var parents = Array(repeating: 0, count: N+1)
var mid = 0.0
for _ in 0..<100 {
    for i in 0..<N+1 {
        parents[i] = i
    }
    
    mid = (left + right) / 2
    if Kruskal(mid:mid) == true {
        left = mid
    } else {
        right = mid
    }
}

if mid < 0 {
    print("0.0000")
} else {
    let midString = String(format: "%.4f", mid)
    print(midString)
}