택배 기사 배정
플래티넘 I의견: 0
물류 센터에 택배 기사 \(N\)명과 배송 건 \(M\)개가 있다. 모든 배송 건은 반드시 누군가에게 배정되어야 한다.
기사 한 명은 하루에 최대 \(C\)개의 배송을 맡을 수 있다. 기사 \(i\)가 배송 \(j\)를 수행할 때 드는 비용 \(w_{ij}\)가 주어지는데, 일부 (기사, 배송) 조합은 거리나 자격 문제로 수행이 불가능할 수 있다.
모든 배송을 빠짐없이 배정하면서 총 비용을 최소로 하고 싶다. 가능한 최소 총비용을 구하여라. 모든 배송을 배정하는 것이 불가능하면 \(-1\)을 출력한다.
\(1 \le N \le 100\)
\(1 \le M \le 100\)
\(1 \le C \le M\)
\(0 \le w_{ij} \le 10^6\) 또는 불가능을 뜻하는 \(-1\)
첫 줄에 \(N\), \(M\), \(C\)가 주어진다.
다음 \(N\)개의 줄에 각각 \(M\)개의 정수가 주어진다. \(i\)번째 줄의 \(j\)번째 값은 \(w_{ij}\)이며, 그 조합이 불가능하면 \(-1\)이 주어진다.
모든 배송을 배정하는 최소 총비용을 출력한다. 불가능하면 \(-1\)을 출력한다.
2 3 2
4 2 -1
3 -1 5
10배송3은 기사2만 가능(비용5). 배송2는 기사1만 가능(비용2). 배송1은 기사1(4) 또는 기사2(3). 기사2가 배송3을 맡았고 한 명이 최대 2건이므로 배송1을 기사2(3)에게 주면 기사1은 배송2(2)만 맡는다. 총 2+3+5=10이 최소이다.
1 3 2
1 1 1
-1기사가 1명뿐인데 한 명이 최대 2건만 가능하고 배송은 3건이므로 모두 배정할 수 없다. -1.
플래티넘 IIriseoj 작성
출처 Original
평가 및 의견
택배 기사 배정
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
택배 기사 배정