Srodne teme

13.07.2001. Interpol
05.09.2001. no N: line -- irc services config
28.09.2002. da li je neko citao Maximum Security
19.08.2002. Tux Racer Problem
06.05.2003. problem sa putanjama
29.09.2004. Kako naci Maximum Minimuma?
11.11.2004. Maximum execution time
16.02.2005. Kako izvuci maximum iz geforce mx440
10.07.2005. Kako saznati maximum procesora
07.01.2006. Sta mislite o ovoj kartici za dizanje e-golda?

Navigacija

Brisanje liste

Lista poslednjih: 16, 32, 64, 128 poruka.

Maximum matching

[es] :: Art of Programming :: Maximum matching	[ Pregleda: 823 \| Odgovora: 5 ]	Postavi temu Odgovori

Autor

stf
Stefan Mišković
Čačak

Član broj: 51276
Poruke: 65
*.171.eunet.yu.

Profil

Maximum matching

^{25.04.2006. u 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

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

^{25.04.2006. u 16:45}

RooTeR
Rajko Nenadov
Detelinara, NS

Član broj: 2386
Poruke: 385
*.ADSL.neobee.net.

Profil

Re: Maximum matching

^{25.04.2006. u 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 ...

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

^{25.04.2006. u 20:27}

stf
Stefan Mišković
Čačak

Član broj: 51276
Poruke: 65
*.151.eunet.yu.

Profil

Re: Maximum matching

^{25.04.2006. u 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]}

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

^{25.04.2006. u 21:22}

NrmMyth
Split, Kaštela

Član broj: 63456
Poruke: 839
*.net.t-com.hr.

Profil

Re: Maximum matching

^{26.04.2006. u 09:05}

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

http://www.last.fm/user/NrmMyth/

^{26.04.2006. u 09:05}

stf
Stefan Mišković
Čačak

Član broj: 51276
Poruke: 65
*.156.eunet.yu.

Profil

Re: Maximum matching

^{26.04.2006. u 10:59}

Citat: