RiseOJ – 우유 펌핑

설명

농부 존은 우유 생산 제국을 확장하기 위해 최근 새 농장을 하나 구입했다. 새 농장은 파이프 네트워크로 근처 마을과 연결되어 있으며, FJ는 농장에서 마을로 우유를 퍼 나르는 데 사용할 파이프들 중 구매하기에 가장 좋은 집합을 찾고 싶다.

파이프 네트워크는 $$N$$ 개의 교차점(파이프의 끝점)으로 설명되며, 편의상 $1 \ldots N$ ( $2 \leq N \leq 1000$ )로 번호가 붙어 있다. 교차점 1은 FJ의 농장을, 교차점 $$N$$ 은 마을을 나타낸다. 양방향 파이프가 $$M$$ 개( $1 \leq M \leq 1000$ ) 있으며, 각 파이프는 두 교차점을 연결한다. $$i$$ 번째 파이프를 FJ가 구매해 사용하는 데 드는 비용은 $$c_i$$ 달러이고, 초당 $$f_i$$ 리터의 우유 유량을 감당할 수 있다.

FJ는 경로 하나를 이루는 파이프들을 구매하고 싶은데, 이 경로의 양 끝점은 교차점 1과 $$N$$ 이어야 한다. 경로의 비용은 경로 위 파이프들의 비용의 합이다. 경로의 유량은 경로 위 파이프들의 유량 중 최솟값이다(경로를 따라 흐르는 유량의 병목이 되기 때문이다). FJ는 경로의 유량을 경로의 비용으로 나눈 값을 최대화하고 싶다. $$1$$ 에서 $$N$$ 으로 가는 경로가 존재함이 보장된다.

문제 제공: Brian Dean

제약

점수 배점

테스트 케이스 2-5는 $N,M\le 100$ 을 만족한다.

문제 제공: Brian Dean

입력 형식

첫째 줄에 $$N$$ 과 $$M$$ 이 주어진다. 다음 $$M$$ 개의 줄에는 각각 네 정수 $$a$$ 와 $$b$$ (파이프가 연결하는 서로 다른 두 교차점), $$c$$ (비용), $$f$$ (유량)로 파이프 하나가 설명된다. 비용과 유량은 모두 $1 \ldots 1000$ 범위의 양의 정수이다.

출력 형식

최적해의 값에 $$10^6$$ 을 곱한 뒤 정수로 버림한 값(즉, 이 수가 정수가 아니라면 그보다 작은 가장 큰 정수로 내림한 값)을 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 pump.in · 출력을 쓸 파일 pump.out

예제 1

입력

3 2
2 1 2 4
2 3 5 3

출력

설명

In this example, there is only one path from $$1$$ to $$N.$$ Its flow is $\min(3,4)=3$ and its cost
is $$2+5=7.$$

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > December > Gold

올림피아드 > USACO > 2019-2020 > December > Gold

태그

JudgeUSACO

우유 펌핑

평가 및 의견

풀이 제출