Preu mínim P20023


Statement
 

pdf   zip

thehtml

Teniu n tasques a realitzar, i n treballadors que poden fer-les. Per a cada tasca 1 ≤ in i cada treballador 1 ≤ jn, p[i][j] és el preu de que el treballador i faci la tasca j.

Feu un programa que calculi el preu mínim d’assignar exactament una tasca diferent a cada treballador.

Entrada

L’entrada consisteix en un natural 1 ≤ n ≤ 10, seguit de p, la matriu n × n de preus (n línies amb n naturals entre 1 i 1000).

Sortida

Escriviu el preu mínim d’assignar exactament una tasca diferent a cada treballador.

Observació

Existeixen algorismes de cost polinòmic per resoldre aquest problema, però són difícils de programar. Implementeu un backtracking.

Public test cases
  • Input

    3
    5 2 1
    2 1 3
    1 3 7
    

    Output

    3
    
  • Input

    4
    2 5 7 9
    2 2 2 2
    2 1 8 3
    2 9 9 8
    

    Output

    12
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++ Python