Iar acum cateva idei despre rezolvare: (in primul rand trimit atasat
sursele celor care au obtinut punctaj maxim)
In primul rand, daca m>n, in mod evident nu exista solutie, deoarece nu
avem suficienti senatori cate fotolii prezidentiale (testul 9).
In afara acestui caz particular, problema este o problema de cuplaj intr-un
graf bipartit. Prima multime de noduri este reprezentata de senatori, iar cea
de-a doua de comisiile parlamentare. In acest graf, avem muchie intre un
senator si o comisie parlamentara doar daca senatorul face parte din respectiva
comisie parlamentara, si deci este un posibil candidat la presedintia comisiei.
O rezolvare posibila pentru o problema de cuplaj este considerarea ei drept
o problema de flux maxim. Pentru aceasta se adauga nodul S, numit nodul sursa,
(care se leaga de toti senatorii) si nodul D, numit nodul destinatie (care se
leaga de toate comisiile). Apoi se aplica algoritmul Ford-Fulkerson, gasindu-se
iterativ drumuri de crestere intre cele doua noduri fictive, S si D. Nu am
sa explic aici algoritmul Ford-Fulkerson (considerandu-l cunoscut), dar daca
exista doritori, sa ma anunte si le voi trimite descrierea lui.
In legatura cu implementarea, cel mai bine este sa se foloseasca 2 matrici
de n linii si m coloane, dar pentru simplitate se putea folosi si o matrice
de n+m linii si n+m coloane.
|
|