R00641
최소 비용 작업 배정
다이아몬드 IV레이팅
의견: 0
설명
\(N\)명의 작업자와 \(N\)개의 작업이 있다. 작업자 \(i\)가 작업 \(j\)를 맡으면 비용 \(c_{i,j}\)가 든다. 각 작업자는 정확히 하나의 작업을, 각 작업은 정확히 한 명의 작업자를 배정받아야 한다.
모든 작업자에게 서로 다른 작업을 빠짐없이 배정할 때, 비용의 총합을 최소로 하는 값을 구하여라. 비용은 음수일 수도 있다.
\(N\)이 최대 \(300\)이므로 모든 배정(\(N!\))을 시도할 수 없다.
제약
\(1 \le N \le 300\)
\(-10^6 \le c_{i,j} \le 10^6\)
입력 형식
첫 줄에 \(N\)이 주어진다.
다음 \(N\)개의 줄에 각각 \(N\)개의 정수가 주어지며, \(i\)번째 줄의 \(j\)번째 수가 \(c_{i,j}\)이다.
출력 형식
최소 비용의 총합을 한 줄에 출력한다.
예제 1
입력
3
4 2 8
4 3 7
3 1 6
출력
12설명
작업자1->작업2(2), 작업자2->작업1(4)... 여러 배정 중 1->1(4), 2->3(7), 3->2(1)을 고르면 합이 12로 최소이다.
예제 2
입력
1
-5
출력
-5설명
작업자가 한 명이면 유일한 배정이며 비용은 \(-5\)이다.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
최소 비용 작업 배정
개요
Log in to rate problems.
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
최소 비용 작업 배정
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기