infoarena

Am urmatoarea problema:

Am o matrice N * N cu elemente numere naturale.

Vreau sa parcurg aceasta matrice de la linia 1 la linia N (alegand cate un element de pe fiecare linie) cu conditia ca odata trecut printr-un element, restul elementelor de pe aceeasi coloana nu mai pot fi parcurse pana la sfarsit. Vreau sa scot o secventa de suma maxima prin acest tip de parcurgere.

Am nevoie de o idee de rezolvare destul de urgent :)

Pai de ce e asa urgent? :)

As prefera o idee decat un raspuns off-topic :)

Daca e urgent urgent sa fie! :indifferent: Poti sa incerci backtracking (generezi permutari). Vezi http://en.wikipedia.org/wiki/Rook_polynomial (http://Vezi http://en.wikipedia.org/wiki/Rook_polynomial)

Backtracking e mult prea lent, N <= 400

Dintr-un element poti merge doar intr-un element adiacent sau in oricare altul?

Un cuplaj de cardinalitate N si cost maxim ? :)

@Andrei
Dintr-un element poti merge in oricare altul pe a carui coloana nu ai mai fost inainte (trebuie ales un element de pe fiecare coloana)

@Mihai
Din cate imi dau seama asa e, ce solutie imi propui? Presupun ca folosesc flux maxim unde reteaua are S care duce in N noduri cu capacitatea infinit, apoi cele N noduri duc in alte N noduri (toate combinatiile posibile) cu capacitatile date de matricea mea si apoi alea duc in T (tot cu capacitatea infinit).

Nu, din S vei avea muchii în N noduri de capacitate 1 și cost 0, din nodul din dreapta i și nodul din stânga j vei avea capacitate 1 și cost -A[ i ][ j ], iar din cele N noduri din dreapta vei avea muchii de capacitate 1 și cost 0 către destinație. Iar apoi dai bătaie cu cuplaj maxim de cost minim. Suma cerută va fi -costul cuplajului.

Nu. E cum a spus Andrei Misarca. Exista si o solutie care nu implica flux , se numeste algoritmul ungar din cate tin minte.

Look:
http://infoarena.ro/problema/cmcm

Poate nu inteleg problema, dar tu trebuie sa alegi un element de pe fiecare coloana a.i suma sa fie maxima, da ?
Atunci de ce nu alegi maximul de pe fiecare coloana si gata, sau imi scapa mie un detaliu ?  ???

Și dacă maximele de pe fiecare coloană sunt pe aceeași linie ce faci?

A, deci acest detaliu imi scapa :-' , thanks :D

Ms de raspunsuri, works wonderfully :)