Solutii Runda 1

Imagine

Strigat

Flux

Vom forma un sistem de ecuatii in care necunoscutele X_i vor fi suma fluxurilor de pe drumul de la 0 la nodul i (care se garanteaza ca este aceeasi indiferent de drum). Fluxul trimis de la i la j va fi exact n_i,j * ( X_j - X_i) unde n_i,j este numarul de muchii dintre i si j. Vom pune conditiile de conservare a fluxului pentru fiecare nod i: suma fluxurilor care intra sa fie egala cu suma fluxurilor care ies. Pentru nodul 1 nu este necesar sa scriem ecuatia deoarece se stie X₁=0, iar pentru nodul N vom pune ecuatia suma fluxurilor care intra in el sa fie 1. Sistemul de N-1 cu N-1 necunoscute se rezolva folosind Gauss.

Pana acum am satisfacut conditiile de flux si restrictia impusa de enunt, mai avem doar de satisfacut restrictiile de capacitate de pe fiecare muchie. Observam ca daca pentru ecuatia pentru nodul N in loc de 1 fixam o valoare S fluxurile trimise pe fiecare muchie se vor inmulti cu S. Asadar pentru a satisface conditiile de capacitate trebuie doar sa inmultim fluxurile de pe fiecare muchie cu minimul dintre F_i,j / C_i,j unde F_i,j este fluxul trimis pe muchie (i,j) si C_i,j este capacitatea muchiei (i,j).