실행 시간 제한 | 메모리 제한 |
---|---|
1 초 | 512 MB |
수현은 최근에 새로운 공장을 구입하여 그의 우유 생산 인프라를 확대했습니다. 새 공장은 인근 마을에 파이프 네트워크를 통해 연결되어 있으며, 수현은 공장에서 마을로 우유를 펌핑하기 위해 사용할 파이프 중 가장 좋은 세트를 고르는 방법을 알아내려고 합니다.
파이프 네트워크는 개의 접점들 (파이프의 끝점들), 편리하게도 까지 번호가 매겨져 있습니다. (). 접점 1은 수현의 공장을 표시하며, 접점 은 마을입니다. 두 접점들을 연결하는 개의 양방향 파이프가 있습니다.() 번째 파이프는 수현이 사용하기 위해 구입하는데 달러가 들고, 리터의 우유를 초당 흐르게 할 수 있습니다.
수현은 접점 1과 이 끝점인 한 개의 경로만 파이프를 구입하려고 합니다. 경로의 비용은 경로를 따라가는 파이프의 비용의 합입니다. 경로를 따라 가는 흐름의 속도는 경로를 따라 가는 파이프 중 가장 작은 흐름의 속도입니다. (이것은 경로를 따라가는 흐름의 병목 현상입니다). 수현은 흐름속도를 경로의 비용으로 나눈 값을 최대화하려고 합니다. 부터 까지의 경로가 존재함이 보장됩니다.
입력의 첫 번째 줄에는 과 이 주어집니다. 이어지는 줄 각각은 네 개의 정수로 파이프를 설명합니다: 와 (파이프로 연결된 두 접점), (비용), (흐름속도). 비용과 흐름속도는 모두 범위의 양의 정수입니다.
3 2 2 1 2 4 2 3 5 3
428571
이 예제에서는 에서 까지의 경로는 하나뿐입니다. 그 흐름은 이고 그 비용은 .
출처: USACO 2019 December Contest, Gold Problem 1. Milk Pumping