026 Arbore partial de cost minim

[•blasterz]

Se poate face si arbore partial de cost maxim tot asa? (de ex la Kruskal sortezi descrescator in loc de crescator)

Cred ca da.

[•Bit_Master]

Mie-mi crapa sort-ul din stl?!? Desi i-am dat domeniul de sortare corect? Crapa in STL.

[•skull]

Cod:

bool muchii_crescatoare(mchie m1, mchie m2)
{
	return m1.cost <= m2.cost;
}

Cred ca daca lasi doar "<" merge.

[•wefgef]

Da, e exact la fel implementarea, cu exceptia sortarii.

[•scipianus]

Se poate lua 100pct cu Kruskal cu sort-ul din STL ? (fara vreun min-heap pentru selectarea mai eficienta a muchiei de cost minim ?) Ca eu am incercat asa si iau doar 80pct cu 2 TLE-uri http://infoarena.ro/job_detail/595463 , am parsat apoi si citirea si tot nu intra cele 2 teste in limita de timp http://infoarena.ro/job_detail/595476  

[•klamathix]

Pai se poate, dar trebuie sa unesti componentele conexe folosind paduri de multimi disjuncte, nu asa cum faci tu, in O(n) . Tu ai complexitate O(N * M), cea buna e O(MlogM + M log*N)

[•valentin.harsan]

imi poate zice ce mai pot optimiza la sursa asta http://infoarena.ro/job_detail/617691?action=view-source? e algoritmul lui Kruskal(cred) dar nu am folosit nici o sortare. Iau TLE pe 3 teste.

[•Grimpow]

pe infoarena iau 1 raspuns gresit si 9 SIGSEV dar eu am rulat programul meu pentru toate testele alaturi cu alt program care ia 100 si nu este nici o diferenta .....
Raspunsul meu:
-17
8
1 5
7 1
3 2
9 7
4 1
6 5
2 6
8 3

Raspunsul unei alte surse de 100 de puncte:
-17
8
1 5
7 1
3 2
9 7
1 4
6 5
2 6
3 8

[•paulbota]

deci nu inteleg ce am gresit la sursa asta imi da bine pe orice test incerc
http://infoarena.ro/job_detail/726851?action=view-source

[•psycho21r]

Testele pentru toate problemele din arhiva educațională sunt publice.

http://infoarena.ro/problema/apm?action=attach-list

[•dragosnicolae]

@paulbota

In functia downheap apelezi upheap(max) in loc de downheap(max)

[•adysnook]

stie cineva care este diferenta dintre
http://infoarena.ro/job_detail/742829?action=view-source
si
http://infoarena.ro/job_detail/742836?action=view-source
?
de ce una primeste 100 si cealalta 70?

[•soriyn]

Probabil pentru ca intr-una folosesti endl si in cealalta "\n"

[•adysnook]

intr-adevar! multumesc mult! am aflat si eu acum ca endl face mai mult decat sa bage un simplu sfarsit de linie.

[•dutzul]

nuntaleg ce problema are sursa mea din cate ma uit pe ea e la fel cu celelalte de 100 folosesc kruskal,, any1 help? thnxhttp://infoarena.ro/job_detail/773689?action=view-source

[•klamathix]

Problema e ca nu folosesti nicio optimizare pentru padurile de multimi disjuncte. Astfel poti sa ai O(n) pe interogarea pentru componenta conexa fiindca arborii aia devin destul de dezechilibrati daca nu-i ajustezi pe parcurs. And also, incearca sa scrii mai corect pe forum 

[•dutzul]

mia mers de 100 cu comprimarea drumului. eu ziceam ca sursa oficiala nu foloseste nici o optimizare(sau asa mi se pare mie) si ia 100
la varianta Prim nu reusesc sa iau peste 80 de pcte zice killed by signal 11 oare dela ce o fi?
http://infoarena.ro/job_detail/773881?action=view-source  .thnx

Editat de admin:
Mi-a mers de 100 cu comprimarea drumului . Eu ziceam ca sursa oficiala nu foloseste nicio optimizare (sau asa mi se pare mie) si ia 100. La varianta Prim nu reusesc sa iau peste 80 de puncte. Zice killed by signal 11. Oare de la ce o fi?

[•danalex97]

La SIGSEGV e de obicei stack overflow sau ai iesit din limitele unui vector. La al 2-lea nu cred ca e cazul. App , tu nu ai complexitate M lg M , nu N lg M ? 

[•swim406]

http://infoarena.ro/job_detail/795688

Nu îmi dau seama de ce nu reuşesc să iau peste 70 de puncte nici cu Kruskal, nici cu Prim. Mă puteţi ajuta careva?

[•PlayLikeNeverB4]

Nu ai complexitatea buna. Uita-te peste explicatiile si sursele de pe pagina problemei.

[•steluta]

am incercat si kruscal si prim, dar nu inteleg de ce la unele teste am "subgraf selectat nu e arbore". are cineva vreo idee?

[•SebiSebi]

Tu afisezi primele n-1 muchii citite, ceea ce nu e corect.  

[•zvon]

In exemplul nr 2 costul minim este calculat gresit.. E de fapt -7 si nu -9. Exemplele acestea au fost evaluate prin acelasi procedeu care evalueaza solutiile trimise de utilizatori? 

[•pauldb]

-9 e mai mic decat -7. 

[•klamathix]

-9 e mai mic decat -7. 

Dar ai folosit aceeasi algebra care evalueaza solutiile trimise de utilizatori?