suport minim

[•Andreid91]

Salut!

Ma uitam pe niste probleme de pe la nationale si am gasit o implementare pentru suportul minim...numai ca nu prea o inteleg

Imi puteti pune va rog frumos niste begin-uri si niste end-uri?

Cod:

Suportul minim se poate calcula în modul următor:

// presupunem că a fost calculat deja un cuplaj maxim
// S este suportul minim, iniţial mulţime vidă
// C(j-dreapta) e nodul i-stânga cu care e cuplat j-dreapta (daca există)

procedura calculează(i-stânga) // doar pt. noduri care nu sunt în suport
	pentru j-dreapta vecin al lui i-stânga
		dacă j-dreapta nu e în S
			S <- S+{j-dreapta}
			S <- S-{ C(j-dreapta) } // există mereu C(j-dreapta)
			calculează( C(j-dreapta) )

pentru fiecare i din stânga
	daca i e cuplat
		S <- S+{i}

pentru fiecare i din stânga
	daca i nu e cuplat
		calculează(i)

Nu inteleg ce ar trebui sa fac al doilea for (cel de la mijloc) si cand ar trebuii folosit... sa pot rula programu sa vad cum se comporta; apoi imi dau eu seama

[•ionutz32]

Al doilea for introduce in suport toate nodurile din stanga care sunt incidente la muchiile din cuplajul maxim, ceea ce asigura ca toate muchiile cuplajului maxim vor avea in suport cel putin un nod. Deoarece suportul minim e egal cu cuplajul maxim, multimea S si-a atins deja cardinalul final, iar in continuare algoritmul doar va scoate din multime elemente pe care le va inlocui cu altele. Sunt parcurse toate nodurile i din stanga care nu au fost cuplate (deci nu se afla nici in multime) si sunt parcursi vecinii lor. Daca se gaseste un vecin j care nu se afla in suport inseamna ca muchia dintre nodurile i si j nu are niciun varf in suport, asa ca se adauga nodul j. Nodul j cu siguranta e cuplat (pentru ca altfel ar fi putut fi cuplat cu nodul i, deci cuplajul nu ar mai fi maxim) cu un nod k. Cum muchia dintre j si k are acum ambele varfuri selectate, k va fi scos si se va lansa aceeasi procedura si pentru el, care verifica daca prin scoaterea lui k a ramas vreo muchie ale carei noduri incidente nu sunt selectate.

[•Andreid91]

uau...ce promt ai fost !

mersi mult !