[ stf @ 25.04.2006. 16:45 ] @
Pre jedno mesečak dana sam uradio na USACO-u neki zadatak sa mečinzima. Ja sam radio preko Network Flow-a što se prošlo relativno brzo, ali sam posle našao na onom njihovom forumu da postoji neko brže rešenje. E sad, zanimaju me dve stvari: 1) Postoji li neki drugi način za rešavanje Maximum matching-a, a da nije preko Network Flow-a? 2) I još nešto: Koliko sam primetio, ako se rešavaju mečinzi ovako kako sam ja radio moguće je samo odrediti koliko iznosi maksimalan broj čvorova, ali ne i koji čvorovi su povezani kojom ivicom u tom mečingu. Pa me zanima kako se to određuje... P.S. Ovo se sve odnosi na biparitne grafove! Pozdrav, Boneli |