파이프(pipe) > 문제은행

본문 바로가기


알고리즘 네트웤플로우

1110 : 파이프(pipe)

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 232 회    시도횟수: 1136 회   



농부 창호는 가뭄에 대비하기 위하여 강으로부터 여러 마을을 거쳐 논까지 파이프를 연결하여 물을 공급하려고 한다. 아래 그림에서 알파벳은 각 마을을 의미하며 화살표의 정수는 파이프의 굵기로서 한 번에 보낼 수 있는 물의 양을 나타낸다.


7ce7f2eba5731c8babe39036322897a0_1449829 


위 그림에서 강에서 논까지 한 번에 보낼 수 있는 물의 양은 다음과 같이 계산하여 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이다.


강과 논 그리고 마을이 주어지고 각각을 잇는 파이프의 용량이 주어질 때 강에서 논까지 한번에 보낼 수 있는 최대 물의 양을 구하는 프로그램을 작성하라.


 


입력의 첫 줄에는 파이프의 수 M과 마을(강과 논 포함)의 수 N이 주어진다. (2≤N≤200, 1≤M≤200)
강의 번호는 1, 논의 번호는 N이며 마을은 2번부터 N-1까지의 번호가 부여된다.
두 번째 줄부터 M개의 줄에는 파이프의 연결상태를 나타내는 세 개의 정수 Si, Ei, Wi가 주어지는데 Si 마을에서 Ei 마을로 Wi만큼의 물을 보낼 수 있다는 의미이다.

마을과 마을 사이에는 파이프의 크기보다 많은 물을 공급하기 위해 여러개의 파이프를 연결할 수도 있다.


강에서 논까지 한 번에 보낼수 있는 최대 물의 양을 출력한다. (출력값은 1억을 넘지 않는다.)

[Copy]
7 6
1 2 7
1 4 6
2 3 3
2 5 6
3 6 4
4 5 9
5 6 8
[Copy]
11


출처 : USACO 93


USACO 93, poj 1273

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.