h1. Doua probleme de la runda 6 a concursului Algoritmus

(Creat de ==user(user="Cosmin" type="tiny")== la data de _2005-01-13_ categoria _Competitii_, autor(i) _Cosmin_)

(Categoria _Competitii_, autor(i) _Cosmin_)

Dupa incheierea brusca a concursului Algoritmus, ideile de rezolvare ale rundei 6 nu au mai aparut pe site. In acest articol va voi prezenta ideile de rezolvare la problemele la care eu am realizat solutiile oficiale.

h2. Problema 4: Joc

Problema cere determinarea numarului maxim de drumuri disjuncte relativ la noduri pornind de la nodul $A$ si terminandu-se in nodul {$B$}. Daca ar fi restrictia numai pentru muchii nu si pentru noduri atunci raspunsul ar fi egal cu fluxul maxim in reteaua de transport formata astfel: sursa e nodul {$A$}, destinatia e nodul $B$ iar orice muchie ({$i,j$}) din graful initial e dublata in reteaua de transport ({$i,j$}) si ({$j,i$}) fiecare muchie avand capacitate {$1$}. Acesta afirmatie e intiutiva, o demonstratie matematica a ei ar fi aplicarea teoremei clasice: fluxul maxim intr-o retea reziduala este egala cu taietura minima in acea retea si a teoremei lui Menger: numarul maxim de drumuri disjuncte relativ la muchii de la $S$ la $T$ este egal cu taietura minima. Problema noastra mai are insa o dificultate, aceea ca trebuie sa nu avem acelasi nod in doua drumuri diferite. Aceasta problema o rezolvam dubland fiecare nod si muchiile ce intrau in nod intra acum in primul dintre cele doua noduri, muchiile ce ieseau ies acum din al doilea nod si mai adaugam o muchie intre primul nod si al doilea nod. Acum drumurile disjuncte relativ la muchii din aceasta retea corespund unor drumuri disjuncte relativ la noduri in prima retea.

Problema cere determinarea numarului maxim de drumuri disjuncte relativ la noduri pornind de la nodul $A$ si terminandu-se in nodul {$B$}. Daca ar fi restrictia numai pentru muchii nu si pentru noduri atunci raspunsul ar fi egal cu fluxul maxim in reteaua de transport formata astfel: sursa e nodul {$A$}, destinatia e nodul $B$ iar orice muchie ({$i,j$}) din graful initial e dublata in reteaua de transport ({$i,j$}) si ({$j,i$}) fiecare muchie avand capacitate {$1$}. Acesta afirmatie e intiutiva, o demonstratie matematica a ei ar fi aplicarea teoremei clasice: fluxul maxim intr-o retea reziduala este egala cu taietura minima in acea retea si a teoremei lui Menger: numarul maxim de drumuri disjuncte relativ la muchii de la $S$ la $T$ este egal cu taietura minima.
 
Problema noastra mai are insa o dificultate, aceea ca trebuie sa nu avem acelasi nod in doua drumuri diferite. Aceasta problema o rezolvam dubland fiecare nod si muchiile ce intrau in nod intra acum in primul dintre cele doua noduri, muchiile ce ieseau ies acum din al doilea nod si mai adaugam o muchie intre primul nod si al doilea nod. Acum drumurile disjuncte relativ la muchii din aceasta retea corespund unor drumuri disjuncte relativ la noduri in prima retea.

Astfel am redus problema initiala la una de flux in graf pe graful transformat. Complexitatea algoritmului e {$O(n*m)$}. Implementarea nu mai dubleaza nodurile la propriu ci foloseste {$c{~i,i~}$} pentru a reprezenta muchia intre cele doua noduri ce reprezinta nodul $i$ din graful initial.