Problem
Você precisa fazer n trabalhos diferentes. Neste caso, você tem uma lista de n trabalhadores braçais e preços, por quantos dólares cada trabalhador faz qual trabalho.
Distribua os trabalhadores para que você gaste menos dinheiro no total. Ao mesmo tempo, você quer fazer tudo em um dia, para que os trabalhadores trabalhem em paralelo. Assim, cada trabalhador realizará exatamente uma tarefa.
Entrada:
Na primeira linha, você recebe um número positivo n (1 <= n <= 8) - o número de empregos e trabalhadores.
As próximas n linhas contêm n inteiros positivos separados por espaços - matriz A, onde A
i,j mostra quantos dólares o trabalhador número i fará o trabalho número j. Para todo A
i,j 1 <= A
i,j <= 10
5.
Saída:
Imprima um único número - o custo mínimo pelo qual você pode contratar esses trabalhadores para todos os trabalhos disponíveis.
Exemplo:
| Entrada |
Saída |
3
3 1 2
5 6 4
7 8 9
| 12 |
Explicação:
O primeiro trabalhador fará o segundo trabalho, o segundo trabalhador o terceiro trabalho e o terceiro trabalhador o primeiro trabalho. O custo total é 1 + 4 + 7 = 12.