[ 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
[ RooTeR @ 25.04.2006. 20:27 ] @
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 ...
[ stf @ 25.04.2006. 21:22 ] @
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:

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


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

[Ovu poruku je menjao stf dana 26.04.2006. u 07:23 GMT+1]
[ NrmMyth @ 26.04.2006. 09:05 ] @
Dali je to "Maximum bipartite matching" ?
Jeli mogu ikako doci do tog maturskog?
[ stf @ 26.04.2006. 10:59 ] @
Citat:
Dali je to "Maximum bipartite matching" ?

Da, to je to.

Citat:
Jeli mogu ikako doci do tog maturskog?

Pogledaj top temu i tamo gde su ''Uparivanja'' imaš u attachment-u.
[ NrmMyth @ 26.04.2006. 20:42 ] @
thx