142 Ciclu

[•greco]

Aici puteţi discuta despre problema Ciclu.

[•alex_prg]

nu pricep o kestie ... calculez costul mediu al unui cilcu .... adica indiferent care ? sau caut ciclul cu costul mediu minim ?

[•filipb]

Logic ca ciclul de cost mediu care sa fie MINIM, adica toate celelalte cicluri au costul mediu mai mare decat cel determinat ca fiind minim.

[VladS]

Pai e suficient numai costul, tu cand cauti costul verifici doar daca exista un ciclu cu costul respectiv, fara a-l determina.

[•pauldb]

Daca printez printf("%.2lf\n",sol) e ok?

[•azotlichid]

da

[•cos_min]

shtiu k suna ... da un ciclu inseamna sa revina in nodul sursa? sau nu?

[•tm_radu]

da

[•Cosmin]

RTM

[•cos_min]

RTM ? ce ii aia ? 

[•Marius]

RTM ? ce ii aia ? 

Read the Manual! 

[•Marius]

Eu incerc sa determin daca exista un ciclu de cost negativ pornind numai din nodul 1 folosind Bellman Ford cu coada, iar acest ciclu exista cand un nod din cele N a fost scos din coada de N ori. Este adevarat ce am zis, pentru ca obtin doar 60 ?

[•wefgef]

ciclul cautat nu contine neaparat nodul 1.

[•Marius]

ciclul cautat nu contine neaparat nodul 1.

Am incercat si asa: am pornit din fiecare nod neexplorat, initializandu-l cu distanta 0, si am aplicat algoritmul lui Bellman Ford cu coada obisnuit si am luat 30.
Poate nu am incercat bine.

[•filipb]

Nici asa nu e bine. Incearca sa introduci un nod auxiliar S, si muchii orientate de cost 0 de la nodul S la fiecare din celelalte noduri si fa un Bellman Ford din sursa S ( astfel vei determina sigur daca exista vreun ciclu negativ ).

[•MarcvsHdr]

Cum poate exista un ciclu negativ, daca fiecare muchie e strict pozitiva si lungimea ciclului este, evident, tot strict pozitiva?

[•DITzoneC]

Se cauta binar costul mediu minim cerut si se scade pe toate muchiile. Pe noile costuri astfel obtinute se cauta ciclul de cost negativ. Daca faci un pic niste formule pe foaie o sa intelegi de ce merge chestia asta.

[•Bluedrop_demon]

Imi puteti divulga si mie unul dintre teste va rog ? Algoritmul meu merge pe exemplu si pe toate testele care i le-am dat eu. Totusi iau numai primul test  Inca un exemplu mi-ar fi de mare folos...

[•Cosmin]

Nu se dau teste oficiale ...

[•Bluedrop_demon]

Nici o problema. Intre timp am descoperit unde am facut greseala. Scuze pentru ce am cerut. Am gresit eu intrebarea, ar fi trebuit doar sa cer cateva teste mari si atat  , in loc sa cer pe cele oficiale. Multumesc oricum!

[•new_programmer]

Cei cu sursele de 1.3 kb ati folosit programare dinamica sau ati rezolvat cu cautare binara+bellman ford?

[•Mishu91]

Este atât de relevantă dimensiunea sursei? Și apoi, nu prea văd cu ce te-ar ajuta dacă ai ști că cei cu surse de 1,3 au rezolvat printr-o metodă sau alta. Deși nu am sursa de 1,3 kb, am rezolvat prin căutare binara + Bellman - Ford.

[•new_programmer]

   Poi ma ajuta sa stiu , deoarece vreau sa stiu daca o iau pe aratura.Eu am o sursa de +3 kb incercand sa fak ce am zis mai sus.
   Daca numarul pe care-l cautam binar e 8/3 cum il gasesti?

[•Mishu91]

Înmulțești costurile tuturor muchiilor cu 100 si cauti un numar intreg, iar când afișezi împarți la 100.

[•new_programmer]

Poi asa faceam , dar de exemplu daka am un graf de genu:
4 5
1 4 5
4 2 5
1 2 1
2 3 3
3 1 4

Ar trebui sa gasesc r=266 care impartit la 100 da 2.66(8/3) pentru ciclu 1-2-3-1.Ca sa fie acest ciclu egal cu 0 ar trebui sa am conditia urmatoare adevarata: 100-r+300-r+400-r=0 <=> -166+34+134=0 <=>166=168 dar e falsa