농부 창호는 가뭄에 대비하기 위하여 강으로부터 여러 마을을 거쳐 논까지 파이프를 연결하여 물을 공급하려고 한다.

아래 그림에서 알파벳은 각 마을을 의미하며 화살표의 정수는 파이프의 굵기로서 한 번에 보낼 수 있는 물의 양을 나타낸다.

위 그림에서 강에서 논까지 한 번에 보낼 수 있는 물의 양은 다음과 같이 계산하여 11임을 알 수 있다.

① 강 → A마을 → B마을 → 논 : 3

② 강 → A마을 → D마을 → 논 : 4

③ 강 → C마을 → D마을 → 논 : 4

②의 경우 강에서 A마을까지 ①에서 이미 3을 보냈으므로 남은 용량은 4이다.

③의 경우 D마을에서 논까지 ②에서 이미 4를 보냈으므로 남은 용량은 4이다.

그렇지만 다음과 같이 계산을 하면 9밖에 보낼 수 없게 된다.

① 강 → A마을 → D마을 → 논 : 6

② 강 → A마을 → B마을 → 논 : 1

③ 강 → C마을 → D마을 → 논 : 2

②의 경우 강에서 A마을까지 ①에서 이미 6을 보냈으므로 남은 용량은 1이다.

③의 경우 D마을에서 논까지 ②에서 이미 6을 보냈으므로 남은 용량은 2이다.

강과 논 그리고 마을이 주어지고 각각을 잇는 파이프의 용량이 주어질 때 ,

강에서 논까지 한번에 보낼 수 있는 최대 물의 양을 구하는 프로그램을 작성하라.

파이프(pipe) timer 1s memory 64MB

파이프(pipe) 1s 64MB