•Marius
|
|
« : Ianuarie 11, 2010, 19:43:44 » |
|
Aici puteţi discuta despre problema Algoritmul Bellman-Ford.
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
•xtreme
|
|
« Răspunde #1 : Februarie 07, 2010, 16:17:43 » |
|
De ce nu comentati sursele alea de 100 de puncte? Puneti tot felul de functii complicate ca sa nu se inteleaga algoritmul in sine.Probabil ca e mai eficient dar e mai bine sa sacrificam pentru simplitate, pentru ca dupa ce intelegi algoritmul si stii si functiile alea "smechere" o sa fie foarte usor sa il optimizezi.
|
|
|
Memorat
|
|
|
|
•CezarMocan
|
|
« Răspunde #2 : Februarie 07, 2010, 16:31:44 » |
|
Care sunt functiile astea complicate?
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #3 : Februarie 07, 2010, 19:16:10 » |
|
@xtreme: Eu cred ca poti sa te exprimi si mai frumos, tu ce zici? Ia incearca.
@cezer: Probabil se refera la STL. Si eu sunt de parere ca sursele oficiale contin prea mult STL in ele.
Ar trebui sa stabilim un standard pentru sursele oficiale din arhiva educationala. Poate vom discuta asta la urmatoarea sedinta.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•gabitzish1
|
|
« Răspunde #4 : Februarie 07, 2010, 22:06:32 » |
|
Am propus si eu chestia asta unor membri din echipa. Cred ca sursele care se dau ca model ar trebui sa fie cat mai aranjate si comentate. Scopul lor (in viziunea mea) e sa clarifice algoritmul, sa ajute la intelegerea lui, nu sa scoata in evidenta dibacia celui ce'a scris'o. Cred ca niste surse aerisite ca aspect si clarificate prin comentarii ar ajuta mai multa lume.
|
|
|
Memorat
|
|
|
|
•xtreme
|
|
« Răspunde #5 : Februarie 10, 2010, 18:10:25 » |
|
Eu zic ca modul de redactare a sursei http://infoarena.ro/job_detail/381834?action=view-source e groaznic.Functiile assert ajuta doar la debugging, dupa ce ne-am asigurat ca programu trece testele aceste functii nu mai au sens.Pentru un tip care vrea sa-nvetze algoritmul, folosirea vectorului adj_t este inutila(probabil ca l-a ajutat pe el la rezolvare).Cand ia toate muchiile care pornesc dintr-un nod pe care tocmai l-a scos din coada verifica daka acest nod i-a fost calculata distanta(dist[nodcur]<INF), aceeasta conditie e intotdeauna adevarata pentru ca nu bagi in coada numai nodurile a caror distanta a fost calculata.Codul pare a fi scris in graba ca si multe alte surse exemplare din arhiva educationala.
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #6 : Februarie 10, 2010, 18:31:26 » |
|
assert este folosit pentru a testa testele, daca se incadreaza in limitele mentionate mai sus.
|
|
|
Memorat
|
|
|
|
•xtreme
|
|
« Răspunde #7 : Februarie 10, 2010, 18:47:36 » |
|
@alexandru :De unde esti? .Precis daca nu spuneai tu nu stiam, nu se subintelege din posturile mele anterioare ca stiam asta? @pentru restu Autorul a fost scump la comentarii , poate sa ma lamureasca cineva de ce e ciclu infinit daca se introduce de N+1 ori acelasi nod in coada?
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #8 : Februarie 10, 2010, 19:04:35 » |
|
Ce zici sa adopti un ton mai politicos? Contrar asteptarii tale, echipa infoarena nu are nici o indatorire in a te ajuta, ce facem noi este munca voluntara. Daca nu iti place cum ne facem treaba si nu stii sa te integrezi frumos in comunitate, poti sa inveti programare in alta parte.
Noi iti oferim un model la aceste probleme, dar toate problemele au sursa libera. Daca vreun aspect nu ti-e clar, poti sa studiezi si ce au facut altii.
|
|
|
Memorat
|
Am zis
|
|
|
•Mishu91
|
|
« Răspunde #9 : Februarie 10, 2010, 21:54:43 » |
|
Eu zic ca modul de redactare a sursei [...] e groaznic.
Să nu ne obrăznicim. Dacă o sursă este redactată într-un stil diferit de al tău nu înseamnă că este groaznică. @pentru restu Autorul a fost scump la comentarii , poate sa ma lamureasca cineva de ce e ciclu infinit daca se introduce de N+1 ori acelasi nod in coada?
Dacă ai fi citit explicațiile de pe wiki (din articolul către care se face legătura), ai fi aflat de ce e așa. Consider ca nu trebuie făcută muncă de transcriere dacă există niște articole deja scrise.
|
|
« Ultima modificare: Februarie 10, 2010, 22:16:34 de către Andrei Misarca »
|
Memorat
|
|
|
|
•toni2007
|
|
« Răspunde #10 : Februarie 10, 2010, 22:26:33 » |
|
Eu zic ca modul de redactare a sursei [...] e groaznic. Sursa oficiala e codata dupa standard, ce codezi tu nu este dupa standard . Eu as zice mai degraba sa inveti tu sa indentezi, decat sa critici. Eu sincer nu prea iti inteleg sursele.
|
|
|
Memorat
|
|
|
|
•Marius
|
|
« Răspunde #11 : Februarie 10, 2010, 23:32:04 » |
|
Eu zic ca modul de redactare a sursei http://infoarena.ro/job_detail/381834?action=view-source e groaznic.Functiile assert ajuta doar la debugging, dupa ce ne-am asigurat ca programu trece testele aceste functii nu mai au sens.Pentru un tip care vrea sa-nvetze algoritmul, folosirea vectorului adj_t este inutila... Nu te supăra, dar eu când am învăţat aceşti algoritmi de bază nu am avut niciun model de sursă şi tare aş fi vrut să am, de orice fel ar fi fost ea. @wefgef Nu ştiu dacă mult STL strică. Nu e deloc greu să cauţi în documentaţie, iar dacă te obişnuieşti cu el atunci nu ai decât de câştigat. LE: Acum ştiu de ce îmi tot scădea Karma.
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
•APOCALYPTO
|
|
« Răspunde #12 : Februarie 23, 2010, 09:16:47 » |
|
Salut! Cu execeptia primului si a ultimului nod din ciclu restul trebuie sa nu se repete(sa fie distincte)?
|
|
|
Memorat
|
|
|
|
•Marius
|
|
« Răspunde #13 : Februarie 23, 2010, 16:41:10 » |
|
Salut! Cu execeptia primului si a ultimului nod din ciclu restul trebuie sa nu se repete(sa fie distincte)? Da
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
•philip
Strain
Karma: 5
Deconectat
Mesaje: 39
|
|
« Răspunde #14 : Martie 02, 2010, 00:32:39 » |
|
Testele din atasamente sunt aceleasi cu cele din raportul evaluatorului ( http://infoarena.ro/job_detail/407086)? Daca verific manual, primesc aceleasi rezultate ca in atasamente, dar evaluatorul imi da incorect la majoritatea testelor.
|
|
|
Memorat
|
|
|
|
|
•S7012MY
|
|
« Răspunde #16 : Iunie 07, 2010, 20:20:19 » |
|
A incercat cineva sa implementeze varianta din introducere in algoritmi? Eu am incercat si nu stiu de ce nu imi da bine pe nici un exemplu. #include <cstdio> #include <cstring> #define INFI 0x3f3f3f3f #define DM 250001 #define DN 50001
struct nod { int x,cost; nod *urm; }*v[DN];
int m,n,dist[DN],pr[DN];
void adaugare(int x,int y,int cost) { nod *p; p=new nod; p->cost=cost; p->x=y; p->urm=v[x]; v[x]=p; }
void relaxare(int u,int v,int cost) { if(dist[v]>dist[u]+cost) { dist[v]=dist[u]+cost; pr[v]=u; } }
bool bellman_ford() { int i; nod *p; for(i=1; i<n; i++) for(p=v[i]; p!=NULL; p=p->urm) relaxare(i,p->x,p->cost); for(i=1; i<n; i++) for(p=v[i]; p!=NULL; p=p->urm) if(dist[i]>dist[p->x]+p->cost) return false; return true; }
void initializareSU() { memset(dist,INFI,sizeof(dist)); memset(pr,0,sizeof(pr)); dist[1]=0; }
void afisare() { nod *p; int k; for(k=1; k<=n; k++) { p=v[k]; printf("%d:",k); while(p) { printf("%d ",p->x); p=p->urm; } printf("\n"); } }
int main() { freopen("bellmanford.in","r",stdin); freopen("bellmanford.out","w",stdout); int i,x,y,c; scanf("%d %d",&n,&m); for(i=1; i<=m; i++) scanf("%d %d %d",&x,&y,&c), adaugare(x,y,c); initializareSU(); if(!bellman_ford()) printf("Ciclu negativ!\n"); else for(i=2; i<=n; i++) printf("%d ",dist[i]); //afisare(); return 0; }
|
|
|
Memorat
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #17 : Ianuarie 04, 2011, 13:00:05 » |
|
Nu stiu ce ai facut tu acolo cu lista vecinilor, dar e ceva mult mai complicat decat e nevoie... sau poate nu inteleg eu Am vazut ca faci coada alocata dinamic, mie mi-a mers si static. De asemenea... long?
|
|
|
Memorat
|
|
|
|
•toni2007
|
|
« Răspunde #18 : Ianuarie 05, 2011, 15:42:20 » |
|
Problema e open-tests. Uite-te pe teste.
|
|
|
Memorat
|
|
|
|
•mrares
Strain
Karma: -5
Deconectat
Mesaje: 21
|
|
« Răspunde #19 : Februarie 22, 2011, 21:59:58 » |
|
Am implementat bellman ford cu coada cu liste si a aparut o problema... Structura e struct lista { int inf,c; lista *nod; } *g[nmax];
si nmax din ce stiu eu inseamna numarul de noduri... si 1 ≤ N ≤ 50 000 din enunt. cu 50 005 iau killed by signal, cu m ( 250 005 ) pus iau la fel killed by signal, bea cu 500 005 iau 100 puncte. E gresit in enunt sau problema este de la mine? Tot ce am modificat a fost doar nmaxul respectiv ca sa obtin 100.
|
|
|
Memorat
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #20 : Februarie 22, 2011, 22:06:17 » |
|
Vezi ca si coada ti-e declarata nmax si, cum un nod poate intra de mai multe ori, exista sanse sa depaseasca acea valoare.
|
|
|
Memorat
|
|
|
|
•BalcauIonut
Strain
Karma: 1
Deconectat
Mesaje: 11
|
|
« Răspunde #21 : Martie 29, 2011, 12:29:59 » |
|
Dumnezeule...am stat o ora chinuinduma sa vad unde am gresit ca sa-mi dau seama ca scrisasem "Ciclu Negativ!" cu N mare Imi vine sa sparg ceva!
|
|
|
Memorat
|
|
|
|
•algotroll
Strain
Karma: 0
Deconectat
Mesaje: 3
|
|
« Răspunde #22 : Februarie 29, 2012, 11:20:02 » |
|
Bellman-Ford cu coada cu prioritate chiar are complexitatea mai mare (O(N*M*log2N)) decat cu coada simpla? (O(N*M)) cf. textului
|
|
|
Memorat
|
|
|
|
•laurion
|
|
« Răspunde #23 : Februarie 29, 2012, 15:29:55 » |
|
Bellman-Ford cu coada cu prioritate chiar are complexitatea mai mare (O(N*M*log2N)) decat cu coada simpla? (O(N*M)) cf. textului
Da, coada de prioritate este un heap, si operatiile au complexitatea O(lg N) pe cand coada simpla este un vector si ai complexitate O(1). Vezi Algoritmul lui Dijkstra din Arhiva Educationala.
|
|
|
Memorat
|
|
|
|
•danalex97
|
|
« Răspunde #24 : Iulie 12, 2012, 18:25:47 » |
|
Am o intrebare , anume de ce cu coada ( queue ) iau 100 si cu un vector care simuleaza o coada ( vector din STL ) iau doar 35 ?
|
|
|
Memorat
|
|
|
|
|