Maximum matching

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

Potpis

If you don't live for something, you will die for nothing.

Pa kada napravish rezidualnu mrezu grafa, one grane koje su tezine 0 pripadaju mechingu.

A sto se tiche drugih metoda za odredjivanje, imash u top temu Srdjanov maturski rad na tu temu ...

Potpis

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Gledao sam taj maturski rad i pogledaću još po nekim linkovima za ove druge metode.

Ali za ovo drugo: Lako je meni da zaključim koji svi čvorovi pripadaju mečingu, ali ne znam kako da odredim (kad nađem Maximum matching) za svaki čvor iz jednog dela grafa (jedne bipatricije) sa kojim je čvorom sparen iz drugog dela grafa...

---------------------------------------
Kasnije:



Nisam isprva ni lepo pročitao šta si napisao.
Sad sam ovo isprobao na primeru i radi.
Hvala ti, pozz!

Potpis

If you don't live for something, you will die for nothing.

Dali je to "Maximum bipartite matching" ?
Jeli mogu ikako doci do tog maturskog?

Da, to je to.


Pogledaj top temu i tamo gde su ''Uparivanja'' imaš u attachment-u.

Potpis

If you don't live for something, you will die for nothing.