Antiga Roma (2) P79161

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. L’emperador ha calculat, per a cada parell (i, j), el benefici M_ij que suposaria per a Roma que la dona ‍i-èsima es casés amb l’home j-èsim.

En aquest problema, l’ordre relatiu tant entre les dones com entre els homes no és arbitrari: la dona 1 té un estatus superior a la dona 2, la qual té un estatus superior a la dona 3, etc, i ‍similarment entre els homes. La tradició impedeix formar dos matrimonis (i₁, j₁) i (i₂, j₂) tals que i₁ < i₂ però j₁ > j₂, perquè a la dona i₁, que és més important que la dona i₂, li ‍tocaria un marit de menys categoria (i a l’inrevés).

Donada M, podeu fer els matrimonis que calgui per maximitzar 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 que n i m es troben entre 1 i 1000, i que tots els M_ij es troben entre 1 i 10⁶.

Sortida

Per a cada cas, escriviu el màxim benefici possible, seguit dels n matrimonis formats: per a cada dona entre 1 i n, escriviu el número del seu marit, o un zero si és millor deixar-la soltera. Amb els jocs de proves donats, la solució serà única. Escriviu una línia amb 10 ‍guions al final de cada cas.

Observació

La solució esperada té cost Θ(n · m) en espai i en temps.