291 Roy-Floyd

[ditzone]

Aici puteţi discuta despre problema Roy-Floyd.

[•cristy]

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...

[•tm_radu]

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

[•cristy]

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

[•cos_min]

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

[•cristy]

asa am facut si eu

[•cos_min]

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

[•cristy]

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

[•Bluedrop_demon]

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 daca e ok. Multumesc )

[•sima_cotizo]

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...

[•c_sebi]

Ce complexitate are algoritmul?
Cu O (n³) imi da TLE pe 50% din teste.

[•CezarMocan]

Ciudat... eu am luat 100 cu O(n^3) aplicand Dijkstra (fara heap) pe fiecare nod...

[•cos_min]

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.

[•c_sebi]

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... 

[•megabyte]

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

[•CezarMocan]

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

[•StTwister]

Intra si Roy-Floyd (a se citi numele problemei)

[•Bluedrop_demon]

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 

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! 

[•vanila0406]

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

[•marius21]

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

[•Bluedrop_demon]

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

                        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!

[•marius21]

Multumesc foarte mult.
Inversam ordinea. Nu cred ca puteam imi dau seama singur de asta. Am luat 100. 

[•nash]

 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 ?

[•Darth_Niculus]

 Mie imi merge fara nici o optimizare speciala..... dar poate ai putea sa ne dai putine detalii....

[•nash]

 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 ....