Problem
Necesitas hacer n trabajos diferentes. En este caso, tiene una lista de n manitas y precios, por cuántos dólares qué trabajador hace qué trabajo.
Distribuye a los trabajadores para que gastes menos dinero en total. Al mismo tiempo, desea hacer todo en un día, por lo que los trabajadores trabajarán en paralelo. Así, cada trabajador realizará exactamente una tarea.
Entrada:
En la primera línea se le da un número positivo n (1 <= n <= 8) - el número de trabajos y trabajadores.
Las próximas n líneas contienen n enteros positivos separados por espacios - matriz A, donde A
i,j muestra cuántos dólares el trabajador número i hará el trabajo número j. Para todo A
i,j 1 <= A
i,j <= 10
5.
Salida:
Imprima un solo número: el costo mínimo por el cual puede contratar a estos trabajadores para todos los trabajos disponibles.
Ejemplo:
| Entrada |
Salida |
3
3 1 2
5 6 4
7 8 9
| 12 |
Explicación:
El primer trabajador hará el segundo trabajo, el segundo trabajador el tercer trabajo y el tercer trabajador el primer trabajo. El costo total es 1 + 4 + 7 = 12.