* PAS 1: Construirea grafului bipartit
* PAS 2: Aflarea cuplajului maximal
==

Primul pas este banal si consta din simple parcurgeri ale matricii. Pentru aflarea cuplajului maximal se poate afla utilizand un algoritm de aflarea a fluxului maxim in reteaua asociata grafului bipartit sau se poate algoritmul bazat pe gasirea succesiva a drumurilor in crestere in graf.

 
Complexitatea finala a algoritmului va fi O(N^2*M^2) deoarece in graful bipartit avem maxim N*M muchii si vom N*M noduri. Cum algoritmul pentru aflarea cuplajului maximal are complexitatea V*E (V = numarul de noduri din graf, E = numarul de muchii din graf) concluzia este evidenta.
 

Complexitatea finala a algoritmului va fi $O(N^2^*M^2^)$ deoarece in graful bipartit avem maxim $N*M$ muchii si vom $N*M$ noduri. Cum algoritmul pentru aflarea cuplajului maximal are complexitatea $V*E$ ($V$ = numarul de noduri din graf, $E$ = numarul de muchii din graf) concluzia este evidenta.

Ca tema, recomand rezolvarea urmatoarelor probleme a caror solutie se bazeaza pe aflarea cuplajului maximal intr-un graf bipartit (in unele cazuri acest lucru insa nu este de ajuns):

1. guards (CEOI 2002)
2. knigths (Baltica 2001) - in solutia oficiala a acestei probleme gasiti mai multe informatii despre notiunea de cuplaj maximal intr-un graf bipartit si problemele inrudite
3. Problema Paznici din runda a patra a concursului Algoritmus (gasiti pe pagina si explicatia solutiei) [2]http://algoritmus.org/probleme/Probleme_Runda04.php
4. [3]http://acm.timus.ru/problem.aspx?space=1&num=1106
5. [4]http://acm.sgu.ru/problem.php?contest=0&problem=234
6. [5]http://acm.sgu.ru/problem.php?contest=0&problem=210
7. [6]http://acm.sgu.ru/problem.php?contest=0&problem=218
8. [7]http://online-judge.uva.es/p/v107/10735.html
9. [8]http://online-judge.uva.es/p/v108/10804.html
10. [9]http://online-judge.uva.es/board/viewtopic.php?t=7462

# $guards (CEOI 2002)$
# $knigths (Baltica 2001)$ - in solutia oficiala a acestei probleme gasiti mai multe informatii despre notiunea de cuplaj maximal intr-un graf bipartit si problemele inrudite
# Problema "Paznici":http://algoritmus.org/probleme/probleme_runda04.php din runda a patra a concursului Algoritmus (gasiti pe pagina si explicatia solutiei)
# "http://acm.timus.ru/problem.aspx?space=1&num=1106":http://acm.timus.ru/problem.aspx?space=1&num=1106
# "http://acm.sgu.ru/problem.php?contest=0&problem=234":http://acm.sgu.ru/problem.php?contest=0&problem=234
# "http://acm.sgu.ru/problem.php?contest=0&problem=210":http://acm.sgu.ru/problem.php?contest=0&problem=210
# "http://acm.sgu.ru/problem.php?contest=0&problem=218":http://acm.sgu.ru/problem.php?contest=0&problem=218
# "http://online-judge.uva.es/p/v107/10735.html":http://online-judge.uva.es/p/v107/10735.html
# "http://online-judge.uva.es/p/v108/10804.html":http://online-judge.uva.es/p/v108/10804.html
# "http://online-judge.uva.es/board/viewtopic.php?t=7462":http://online-judge.uva.es/board/viewtopic.php?t=7462

Mentionez ca problema 8 m-a impresionat in mod placut fiind una dintre cele mai frumoase probleme pe care le-am intalnit in ultimele cateva luni.

References
Visible links

2. http://algoritmus.org/probleme/probleme_runda04.php

2.

3. http://acm.timus.ru/problem.aspx?space=1&num=1106
4. http://acm.sgu.ru/problem.php?contest=0&problem=234
5. http://acm.sgu.ru/problem.php?contest=0&problem=210