5267 : A68 - 최대 유량
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$ 개의 탱크와 $M$ 개의 파이프가 있습니다. $j$ 번째 파이프는 탱크 $A_j$ 에서 탱크 $B_j$ 방향으로 초당 $C_j$ 리터까지 물을 흘려보낼 수 있습니다.
탱크 1에서 탱크 $N$ 까지 초당 최대 몇 리터의 물을 흘려보낼 수 있습니까? 탱크에 물을 저장할 수는 없다고 가정합니다.
[제약 조건]
• $2 \le N \le 400$
• $1 \le M \le 400$
• $1 \le A_j , B_j \le N$
• $A_j \neq B_j$
• $j\neq k$ 이면 $(A_j,B_j) \neq (A_k,B_k)$
• $0 \le C_j \le 5000$
• 답은 $5000$ 이하의 정수입니다.
• 입력되는 모든 값은 정수입니다.
탱크 1에서 탱크 $N$ 까지 초당 최대 몇 리터의 물을 흘려보낼 수 있습니까? 탱크에 물을 저장할 수는 없다고 가정합니다.
[제약 조건]
• $2 \le N \le 400$
• $1 \le M \le 400$
• $1 \le A_j , B_j \le N$
• $A_j \neq B_j$
• $j\neq k$ 이면 $(A_j,B_j) \neq (A_k,B_k)$
• $0 \le C_j \le 5000$
• 답은 $5000$ 이하의 정수입니다.
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 $N, M$ 이 주어집니다.
둘째 줄부터 $M$ 개의 줄에 걸쳐 파이프 정보가 주어집니다.
둘째 줄부터 $M$ 개의 줄에 걸쳐 파이프 정보가 주어집니다.
출력 설명
최대 유량을 출력하세요.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
6 7
1 2 5
1 4 4
2 3 4
2 5 7
3 6 3
4 5 3
5 6 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
8