Antiga Roma (1) P73252


Statement
 

pdf   zip

thehtml

Considereu una civilització com la romana, tradicional i jerarquitzada. Hi ha n dones nobles solteres (enumerades entre 1 i n) i m homes nobles solters (enumerats entre 1 i m) en edat de casar-se, amb n ≤ m. L’emperador ha calculat, per a cada parell (i, j), el benefici Mij que suposaria per a Roma que la dona i-èsima es casés amb l’home j-èsim.

Donada la matriu M, podeu fer n matrimonis tot maximitzant el benefici per a Roma?

Entrada

L’entrada consisteix en diversos casos, cadascun amb n i m, seguides de la matriu M: n files amb m naturals cadascuna. Suposeu 1 ≤ n ≤ m ≤ 9, i que tots els Mij es troben entre 1 i 106.

Sortida

Per a cada cas, escriviu el màxim benefici possible. A continuació, si hi ha més d’una solució òptima, digueu quantes n’hi ha. Altrament, si només n’hi ha una, digueu, per a cada dona entre 1 i n, el número del seu marit. Escriviu una línia amb 10 guions al final de cada cas.

Public test cases

  • Input

    2 2
23 42
30 37

3 3
90 10 20
40 30 70
10 80 10

2 3
1 1 1
1 1 1

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

    Output

    benefici: 72
2
1
----------
benefici: 240
1
3
2
----------
benefici: 2
6 solucions
----------
benefici: 23
3
4
5
1
----------
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++