Manies interpersonals P98089

Donades n persones i la mania que es tenen entre si, escolliu com fer-les seure en una taula allargada de manera que la suma de les manies interpersonals de les persones veïnes es minimitzi, amb una restricció: la persona aseguda més a l’esquerra ha de ser la primera persona donada.

Entrada

L’entrada consisteix en diversos casos, cadascun amb n, seguit de n noms diferents, seguit d’una matriu n × n de naturals entre 0 i 10⁶, on la posició (i, j) conté la mania entre les persones i i j. La matriu és simètrica, amb zeros a la diagonal. Assumiu 1 ≤ n ≤ 12.

Sortida

Per a cada cas, escriviu la mínima suma de manies que es pot aconseguir, seguida de la disposició òptima de les persones a taula. Els jocs de proves són tals que sempre hi ha una única solució.