상품 운송 비용 최소화
플래티넘 II의견: 0
\(N\)개의 창고와 \(M\)개의 매장이 있다. 창고 \(i\)에는 \(s_i\)개의 상품이 있고, 매장 \(j\)는 정확히 \(d_j\)개를 받아야 한다. 창고 \(i\)에서 매장 \(j\)로 상품 한 개를 보내는 데 \(c_{i,j}\)의 운송비가 든다.
모든 매장의 수요를 충족하는 것이 가능하면 최소 운송비를, 불가능하면 -1을 출력하라. (고전적인 운송 문제로, 최소 비용 최대 유량으로 푼다.)
\(1 \le N,M \le 100\), \(0 \le s_i \le 2000\), \(1 \le d_j \le 2000\), \(0 \le c_{i,j} \le 10^4\)
첫 줄에 \(N\), \(M\). 둘째 줄에 \(s_1 \dots s_N\). 셋째 줄에 \(d_1 \dots d_M\). 다음 \(N\)개의 줄에 각 줄 \(M\)개의 정수 \(c_{i,j}\).
최소 운송비 또는 불가능하면 -1을 한 줄에 출력한다.
2 3
5 5
3 4 3
2 3 1
4 1 2
14수요 합 10과 공급 합 10이 일치하며, 운송비를 최소화하도록 보내면 최소 비용이 나온다.
1 1
2
5
3
-1공급 2가 수요 5보다 부족하므로 -1.
riseoj 작성
출처 Original
평가 및 의견
상품 운송 비용 최소화
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
상품 운송 비용 최소화