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_1, j_1)$ i $(i_2, j_2)$ tals que $i_1 < i_2$ però $j_1 > j_2$, perquè a la dona $i_1$, que és més important que la dona $i_2$, 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^6$.

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 $\Theta(n \cdot m)$ en espai i en temps.