송유관 최대 처리량
플래티넘 III의견: 0
정유 단지에는 \(N\) 개의 펌프장이 있고, 펌프장 사이는 단방향 송유관으로 연결되어 있다. 각 송유관 \((u, v, c)\) 는 펌프장 \(u\) 에서 \(v\) 방향으로 시간당 최대 \(c\) 리터의 기름을 흘려보낼 수 있다.
공급원 펌프장 \(S\) 에서 출발하여 도착지 펌프장 \(T\) 까지, 송유관 용량 제약을 지키면서 시간당 보낼 수 있는 기름의 최대 총량을 구하여라. 각 중간 펌프장에서는 들어온 양과 나가는 양이 같아야 한다(보존 법칙). 같은 방향의 평행 송유관이 여러 개 존재할 수 있으며, 이 경우 용량은 합산된다.
\(S\) 에서 \(T\) 로 가는 경로가 전혀 없으면 최대 처리량은 \(0\) 이다.
- \(2 \le N \le 500\)
- \(0 \le M \le 5000\)
- \(1 \le u, v \le N\), \(u \ne v\)
- \(0 \le c \le 10^9\)
- \(1 \le S, T \le N\), \(S \ne T\)
첫 줄에 펌프장 수 \(N\), 송유관 수 \(M\), 공급원 \(S\), 도착지 \(T\) 가 공백으로 주어진다.
이어지는 \(M\) 개의 줄에 각각 송유관 정보 \(u\ v\ c\) 가 주어진다.
시간당 보낼 수 있는 기름의 최대 총량을 정수 한 줄로 출력한다.
4 5 1 4
1 2 3
1 3 2
2 3 2
2 4 2
3 4 3
5\(1\to2\to4\) 로 \(2\), \(1\to3\to4\) 로 \(2\) 를 보낼 수 있다. 도착지로 들어오는 용량 합 \(2+3=5\) 이내, 공급원에서 나가는 용량 합 \(3+2=5\) 이내이므로 최댓값은 \(4\) 이다.
4 2 1 4
1 2 5
3 4 7
0\(1\) 에서 \(4\) 로 도달하는 경로가 없으므로 처리량은 \(0\) 이다.
riseoj 작성
출처 Original
평가 및 의견
송유관 최대 처리량
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
송유관 최대 처리량