Pagini: [1] 2   În jos
  Imprimă  
Ajutor Subiect: 291 Roy-Floyd  (Citit de 16141 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
ditzone
Vizitator
« : Octombrie 15, 2006, 21:38:57 »

Aici puteţi discuta despre problema Roy-Floyd.
Memorat
cristy
De-al casei
***

Karma: 2
Deconectat Deconectat

Mesaje: 136



Vezi Profilul
« Răspunde #1 : Octombrie 16, 2006, 21:09:29 »

la problema roy-floyd
1. a ramas limita de 1 secunda, pe cand in concurs era 0.4 secunde
2. cred ca nu am inteles bine problema(desi e una arhicunoscuta):
   am v[j] dist minima intre i si j
        d[j] numarul maxim de drumuri intre i si j
    am inlocuit v[j] si d[j] daca: dist gasita e mai mica decat cea curenta intre i si j sau daca distantele sunt egale si d[k]+d[k][j]>d[j] ce nu e bine? am 15 pct si restu WA...
Memorat

... lipsa de inspiratie ...
tm_radu
De-al casei
***

Karma: 16
Deconectat Deconectat

Mesaje: 140



Vezi Profilul
« Răspunde #2 : Octombrie 16, 2006, 21:13:18 »

pai...d(i)(j) trebuie sa reprezinte numarul maxim de arce ce le poate avea un drum intre i si j...
Memorat

Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
cristy
De-al casei
***

Karma: 2
Deconectat Deconectat

Mesaje: 136



Vezi Profilul
« Răspunde #3 : Octombrie 16, 2006, 21:43:08 »

scuze de exprimare, d[j] reprezinta numarul maxim de arce intre i si j
Memorat

... lipsa de inspiratie ...
cos_min
Nu mai tace
*****

Karma: 48
Deconectat Deconectat

Mesaje: 493


live


Vezi Profilul
« Răspunde #4 : Octombrie 16, 2006, 21:51:25 »

uite cum am facut eu :
1.daca gasesc un drum minim intre i si j, actualizez si nr maxim de arce intre i si j
2.daca gasesc un drum egal cu cel minim intre i si j , actualizez si nr maxim de arce intre i si j (daca este nevoie)

sper ca se intelege ! spor Tongue
Memorat

vid...
cristy
De-al casei
***

Karma: 2
Deconectat Deconectat

Mesaje: 136



Vezi Profilul
« Răspunde #5 : Octombrie 16, 2006, 22:30:51 »

asa am facut si eu Brick wall
Memorat

... lipsa de inspiratie ...
cos_min
Nu mai tace
*****

Karma: 48
Deconectat Deconectat

Mesaje: 493


live


Vezi Profilul
« Răspunde #6 : Octombrie 17, 2006, 16:27:54 »

ai initializat la inceput matr care tine minte nr maxim de arcuri intre i si j ??
Memorat

vid...
cristy
De-al casei
***

Karma: 2
Deconectat Deconectat

Mesaje: 136



Vezi Profilul
« Răspunde #7 : Octombrie 17, 2006, 17:49:03 »

da, am initializat matricea de drumuri cu d[j]=1 in afara de diagonala principala
Memorat

... lipsa de inspiratie ...
Bluedrop_demon
Client obisnuit
**

Karma: -3
Deconectat Deconectat

Mesaje: 66



Vezi Profilul
« Răspunde #8 : Aprilie 01, 2007, 00:13:31 »

Ceva cu siguranta nu e in regula, am scris acelasi algoritm si in pascal si in C si tot iau maxim 15 puncte, mai e oare o conditie? A facut-o cineva de 100 sa ma lumineze si pe mine ?

am facut roy-floyd si pentru suma a[i,k] + a[k,j] = a[i,j] verific daca b[i,k] + b[k,j] > b[i,j] sa actualizez si matricea cu numarul maxim de drumuri...

In rest primesc "Incorrect"
Someone pls help...

LE: Am sa va rog sa ma scuzati ca pun itrebari la probleme asa vechi despre care nu "a mai adus nimeni vorba" de luni bune. Sunt relativ nou pe site si incerc sa rezolv orice problema imi iese in cale. ( Am zis asta pentru ca citeam topicul de Xor Max unde suntem indemnati sa ne uitam la articole la solutie... numai ca era la articole cu muuult timp in urma - daca mai sunt pe undeva solutiile sau macar hint-uri si pentru problemele mai vechi va rog sa-mi dati si mie acces sad daca e ok. Multumesc )
« Ultima modificare: Aprilie 01, 2007, 00:33:13 de către Pandia Gheorghe » Memorat
sima_cotizo
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 596



Vezi Profilul
« Răspunde #9 : Aprilie 01, 2007, 07:15:35 »

Problema asta a fost propusa la concursul "Happy Coding 2006", din cate imi aduc aminte, deci nu foarte demult... Eu cand am implementat-o greseam ordinea for-urilor, in loc de (k,i,j) pusesem (i,j,k)... verifica sa nu fi facut si tu la fel...
Memorat
c_sebi
Client obisnuit
**

Karma: 24
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #10 : Aprilie 01, 2007, 10:51:45 »

Ce complexitate are algoritmul?
Cu O (n3) imi da TLE pe 50% din teste.
Memorat
CezarMocan
Nu mai tace
*****

Karma: 252
Deconectat Deconectat

Mesaje: 567



Vezi Profilul
« Răspunde #11 : Aprilie 01, 2007, 11:17:47 »

Ciudat... eu am luat 100 cu O(n^3) aplicand Dijkstra (fara heap) pe fiecare nod...
Memorat
cos_min
Nu mai tace
*****

Karma: 48
Deconectat Deconectat

Mesaje: 493


live


Vezi Profilul
« Răspunde #12 : Aprilie 01, 2007, 11:34:37 »

Citat
Cu O (n3) imi da TLE pe 50% din teste.

Intra fara probleme. Vezi sa nu intri pe undeva in ciclu' sau nu stiu dc nu iti intra in timp.
Memorat

vid...
c_sebi
Client obisnuit
**

Karma: 24
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #13 : Aprilie 01, 2007, 11:52:50 »

Cod:
void Roy_Floyd ()
{ int i, j, k;
 for (k=1; k<=n; k++)
   for (i=1; i<=n; i++)
     for (j=1; j<=n; j++)
       if (f[i][j] > f[i][k] + f[k][j] && (i!=j))
          {f[i][j] = f[i][k] +f[k][j];
           d[i][j] = d[i][k] + d[k][j];
          }
      else if (f[i][j] == f[i][k] + f[k][j] && (i!=j))
              if (d[i][j] < d[i][k] + d[k][j])
                    d[i][j] = d[i][k] + d[k][j];
}

Asa am facut (+citire +afisare). spuneti-mi pls care e problema...  Think
Memorat
megabyte
Client obisnuit
**

Karma: 45
Deconectat Deconectat

Mesaje: 74



Vezi Profilul
« Răspunde #14 : Aprilie 01, 2007, 12:07:42 »

nu inteleg de ce folosesti 2 matrice de costuri, ideea algoritmului roy floyd este ca daca poti mari( micsora) valoarea drumului de la i la j cu nodul intermediar k. Algoritmul il gasesti in foarte multe carti , se studiaza in clasa a XI-a si poti sa-l gasesti pe google , astai primul rezultat : http://andybyte.lx.ro/c++/roy_floyd.htm Thumb up
Memorat

Toate computerele asteapta cu aceeasi viteza.
CezarMocan
Nu mai tace
*****

Karma: 252
Deconectat Deconectat

Mesaje: 567



Vezi Profilul
« Răspunde #15 : Aprilie 01, 2007, 12:33:31 »

Nu stiu pe unde am auzit ca algoritmul Roy-Floyd nu intra in timp la problema asta...  Whistle. Daca vrei poti incerca Dijkstra.
Memorat
StTwister
Client obisnuit
**

Karma: 11
Deconectat Deconectat

Mesaje: 86



Vezi Profilul
« Răspunde #16 : Aprilie 01, 2007, 12:36:11 »

Intra si Roy-Floyd (a se citi numele problemei)
Memorat
Bluedrop_demon
Client obisnuit
**

Karma: -3
Deconectat Deconectat

Mesaje: 66



Vezi Profilul
« Răspunde #17 : Aprilie 01, 2007, 13:56:32 »

Intr-adevar gresisem ordinea forurilor [i,j,k] in loc de [k,i,j] desi am scris algoritmul de 2 ori. Observasem acest lucru (m-am uitat intr-o carte) dar nu mi s-a parut relevant, mai ales ca pe exemple da bine si [i,j,k]. Am facut pe hartie un test mai mare si am inteles de ce e corect asa. Destul de dragutz! Bine ca m-am prins acuma ca nu mi-as fi dat seama si faceam [i,j,k] "pana la moarte!"

Multumesc! am luat 100p  Ok

P.S. Pt. "sebi" - citirea si scrierea sper ca le-ai facut cu functiile din <stdio.h>  - stream-urile sunt mai lente. Si inca ceva: Daca in matricile f si d ai 0 pe diagonala principala, nu ai nevoie sa verifici ( i != j ) care iarasi "mananca" din timp! Good luck!  Banana
« Ultima modificare: Aprilie 01, 2007, 14:16:07 de către Pandia Gheorghe » Memorat
vanila0406
De-al casei
***

Karma: -174
Deconectat Deconectat

Mesaje: 107


Be wise,be smart,be like me!


Vezi Profilul
« Răspunde #18 : Aprilie 01, 2007, 23:52:28 »

aveam si eu exact aceeasi greseala...de un an incerc sami dau seama ce are...oricum multumesc de hint...acum am 100  Banana
Memorat

Only one thing I know:Death is the best way to a better life.
marius21
Strain
*

Karma: -20
Deconectat Deconectat

Mesaje: 27



Vezi Profilul
« Răspunde #19 : Aprilie 06, 2007, 10:13:27 »

Am o problema:
am facut ordinea forurilor buna am calculat nr maxim de arce bine(cred) dar nu im dau seama ce are

Cod:
Cod sters
« Ultima modificare: Aprilie 07, 2007, 09:01:43 de către Bogdan Tataroiu » Memorat
Bluedrop_demon
Client obisnuit
**

Karma: -3
Deconectat Deconectat

Mesaje: 66



Vezi Profilul
« Răspunde #20 : Aprilie 06, 2007, 14:47:54 »

Buna marius. Eu am observat 2 probleme, dar nu garantez ca asta e cauza:

Citat
                        if (a[i,j]=a[i,k]+a[k,j]) and (b[k,i]+b[k,j]>b[j,i] ) then
                            b[i,j]:=b[i,k]+b[k,j];

1. Nu inteleg de ce compari b[k,i]+b[k,j]>b[j,i]  si apoi atribui b[i,j] := b[i,k]+b[k,j] ? adica le pui pe dos. Prima comparatie ar trebuie sa fie b[i,k]+b[k,j] > b[i,j] nu invers cum ai pus tu. Ai inversat atat i si j cat si i si k.
2. De obicei e bine sa pui caracterul "sfarsit de linie" dupa ultimele date scrise in fisier, daca nu se precizeaza altfel in enunt. Deci dupa ce afisezi matricea b poti sa mai pui un writeln.

In rest pare corect.

P.S. Nu e bine sa postezi surse. Adminii iti vor sterge mesajul!

Memorat
marius21
Strain
*

Karma: -20
Deconectat Deconectat

Mesaje: 27



Vezi Profilul
« Răspunde #21 : Aprilie 06, 2007, 21:58:37 »

Multumesc foarte mult. Very Happy
Inversam ordinea. Nu cred ca puteam imi dau seama singur de asta. Am luat 100.  Winner 1st place
Memorat
nash
De-al casei
***

Karma: 0
Deconectat Deconectat

Mesaje: 109



Vezi Profilul
« Răspunde #22 : Aprilie 17, 2007, 18:05:59 »

 Am implementat si eu aceasta problema .. si .. pe 50% din teste imi da TLE ... si nu vad cum as putea sa mai imbunatatesc ... vre-o idee se poate ?
Memorat
Darth_Niculus
De-al casei
***

Karma: -13
Deconectat Deconectat

Mesaje: 143



Vezi Profilul
« Răspunde #23 : Aprilie 17, 2007, 20:25:17 »

 Mie imi merge fara nici o optimizare speciala..... dar poate ai putea sa ne dai putine detalii....
Memorat
nash
De-al casei
***

Karma: 0
Deconectat Deconectat

Mesaje: 109



Vezi Profilul
« Răspunde #24 : Aprilie 18, 2007, 00:14:32 »

 pai .. solutia e simpla ...
 aplic royfloyd ... si caut sa micsorez distantele ... in cazul in care am gasit acesi distanta... caut sa maximizez numarul de muchii in cazul in care am gasit un drum mai mic... micsorez drumul si reactolizez numarul de muchii ....
Memorat
Pagini: [1] 2   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines