Problem
n 개의 다른 작업을 수행해야 합니다. 이 경우, 어떤 작업자가 어떤 작업을 수행하는지에 대한 n명의 핸디맨 및 가격 목록이 있습니다.
총 비용을 적게 지출하도록 근로자를 분배하십시오. 동시에 하루에 모든 작업을 수행하기를 원하므로 작업자가 병렬로 작업합니다. 따라서 각 작업자는 정확히 하나의 작업을 수행합니다.
입력:
첫 번째 줄에는 양수 n(1 <= n <= 8)이 주어집니다. 이는 일자리와 노동자의 수입니다.
다음 n 줄에는 공백으로 구분된 n 개의 양의 정수가 포함됩니다. 행렬 A, 여기서 A
i,j는 작업자 번호 i가 번호 j에서 일할 금액을 보여줍니다. 모든 A
i,j 1 <= A
i,j <= 10
5.
출력:
하나의 숫자를 인쇄하십시오 - 사용 가능한 모든 작업에 대해 이러한 근로자를 고용할 수 있는 최소 비용입니다.
예:
<몸>
| 입력 |
출력 |
3
3 1 2
5 6 4
7 8 9
| 12 |
설명:
첫 번째 일꾼이 두 번째 일을, 두 번째 일꾼이 세 번째 일을, 세 번째 일꾼이 첫 번째 일을 할 것입니다. 총 비용은 1 + 4 + 7 = 12입니다.