R00420
일꾼 배정과 최소 비용
플래티넘 II레이팅
의견: 0
설명
회사에 \(N\)명의 일꾼과 \(N\)개의 작업이 있다. 일꾼 \(i\)에게 작업 \(j\)를 맡기면 \(C_{i,j}\)의 비용이 든다. 각 일꾼은 정확히 하나의 작업을, 각 작업은 정확히 한 명의 일꾼을 맡아야 한다. 모든 작업을 배정했을 때 드는 총 비용의 최솟값을 구하라.
이 문제는 최소 비용 완전 매칭(최소 비용 최대 유량)으로 해결할 수 있다.
제약
\(1 \le N \le 200\), \(0 \le C_{i,j} \le 10^6\)
입력 형식
첫 줄에 정수 \(N\). 다음 \(N\)개의 줄에 각 줄마다 \(N\)개의 정수 \(C_{i,j}\) (\(0 \le C_{i,j} \le 10^6\)).
출력 형식
총 배정 비용의 최솟값을 한 줄에 출력한다.
예제 1
입력
3
4 1 3
2 0 5
3 2 2
출력
5설명
일꾼1→작업2(1), 일꾼2→작업1(2), 일꾼3→작업3(2)으로 배정하면 총 \(1+2+2=5\)로 최소이다.
예제 2
입력
2
5 9
10 3
출력
8설명
일꾼1→작업1(5), 일꾼2→작업2(3)이면 총 \(8\). 다른 배정 \(9+10=19\)보다 작다.
문제 시리즈
플래티넘 I문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
일꾼 배정과 최소 비용
개요
Log in to rate problems.
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
일꾼 배정과 최소 비용
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기