지진 복구
시간 제한2초메모리 제한128 MB
비용과 시간이 있는 그래프에서 (F - 총비용)/총시간을 최대화하는 신장트리를 찾는 문제로, 이분탐색과 MST를 결합해야 합니다.
문제
정점 N개와 양방향 간선 M개가 있는 그래프가 있다. 지진으로 모든 간선이 끊어졌으므로, 주어진 간선들 중 일부를 복원하여 어떤 정점에서 다른 어떤 정점으로도 이동할 수 있게 만들려고 한다. 즉, 복원한 간선들이 모든 정점을 연결해야 한다.
복원에 사용할 수 있는 기준 금액 F가 주어진다. 각 간선에는 복원 비용 c와 복원 시간 t가 있다. 같은 두 정점을 잇는 간선이 여러 번 주어질 수 있으며, 이 경우 비용이나 시간이 서로 다를 수 있다. 총 복원 비용이 F를 넘더라도 모든 정점을 연결하는 방법은 항상 존재하도록 입력이 주어진다.
복원한 간선들의 총비용을 C, 총시간을 T라고 하자. 얻는 이득은 F - C이고, 시간당 이득은 (F - C) / T이다. 시간당 이득이 최대가 되도록 간선들을 복원했을 때의 값을 구하라.
입력
첫째 줄에 세 정수 N, M, F가 주어진다.
다음 M개의 줄에는 간선 정보 i j c t가 주어진다. i와 j는 간선이 잇는 두 정점의 번호이고, c는 복원 비용, t는 복원 시간이다.
제한은 다음과 같다.
4 <= N <= 4001 <= M <= 10,0001 <= F <= 2,000,000,0001 <= c, t <= 2,000,000,000
출력
시간당 얻을 수 있는 최대 이득을 소수점 아래 넷째 자리까지 출력한다. 최대 이득이 양수가 아니면 0.0000을 출력한다.
힌트
공개 테스트에서는 입력에 주어진 2번, 3번, 4번, 5번 간선을 복원하는 것이 최적이다. 이때 총비용은 83, 총시간은 16이므로 이득은 100 - 83 = 17이고 시간당 이득은 17 / 16 = 1.0625이다.