Problem
Devi fare n lavori diversi. In questo caso, hai un elenco di n tuttofare e prezzi, per quanti dollari quale lavoratore fa quale lavoro.
Distribuisci i lavoratori in modo da spendere meno soldi in totale. Allo stesso tempo, vuoi fare tutto in un giorno, quindi i lavoratori lavoreranno in parallelo. Pertanto, ogni lavoratore eseguirà esattamente un'attività.
Inserimento:
Nella prima riga viene assegnato un numero positivo n (1 <= n <= 8) - il numero di lavori e lavoratori.
Le successive n righe contengono n numeri interi positivi separati da spazi - matrice A, dove A
i,j mostra quanti dollari il lavoratore numero i farà il lavoro numero j. Per tutti A
i,j 1 <= A
i,j <= 10
5.
Uscita:
Stampa un numero unico: il costo minimo per il quale puoi assumere questi lavoratori per tutti i lavori disponibili.
Esempio:
| Input |
Uscita |
3
3 1 2
5 6 4
789
| 12 |
Spiegazione:
Il primo lavoratore farà il secondo lavoro, il secondo lavoratore il terzo lavoro e il terzo lavoratore il primo lavoro. Il costo totale è 1 + 4 + 7 = 12.