레이팅 미적용설명
회사에 \(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\)보다 작다.
문제 시리즈
문제 정보
riseoj 작성
출처 Original
태그