|
Titlul: suport minim Scris de: Ciocan Andrei din Ianuarie 04, 2010, 21:00:04 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?:D Cod: Suportul minim se poate calcula în modul următor: 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 :) Titlul: Răspuns: suport minim Scris de: Ilie Ionut din Ianuarie 04, 2010, 21:43:54 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.
Titlul: Răspuns: suport minim Scris de: Ciocan Andrei din Ianuarie 04, 2010, 21:51:05 uau...ce promt ai fost !
mersi mult ! :thumbup: |