Problem
Vous devez faire n différents travaux. Dans ce cas, vous avez une liste de n bricoleurs et des prix, pour combien de dollars quel travailleur fait quel travail.
Répartissez les travailleurs de manière à dépenser moins d'argent au total. En même temps, vous voulez tout faire en une journée, donc les ouvriers travailleront en parallèle. Ainsi, chaque travailleur effectuera exactement une tâche.
Saisie :
Dans la première ligne, on vous donne un nombre positif n (1 <= n <= 8) - le nombre d'emplois et de travailleurs.
Les n lignes suivantes contiennent n entiers positifs séparés par des espaces - matrice A, où A
i,j indique combien de dollars le travailleur numéro i effectuera le travail numéro j. Pour tout A
i,j 1 <= A
i,j <= 10
5.
Sortie :
Imprimez un seul chiffre - le coût minimum pour lequel vous pouvez embaucher ces travailleurs pour tous les emplois disponibles.
Exemple :
| Entrée |
Sortie |
3
3 1 2
5 6 4
7 8 9
| 12 |
Explication :
Le premier travailleur effectuera le deuxième travail, le deuxième travailleur le troisième travail et le troisième travailleur le premier travail. Le coût total est 1 + 4 + 7 = 12.