283 Cc

[ditzone]

Aici puteţi discuta despre problema Cc.

[•peanutz]

Fac un vector de struct cu 3 variabile: copil, calc si cost.... apoi sortez dupa cost. Si fac un greedy luand pe cele de la inceput si adaugand in costmin daca nu figureaza intr-un vector uz dupa care adaug elementul actual in uz(atat calc cat si copil)... E bun algoritmul sau incomplet?

[Chris]

Nu e nici bun, nici incomplet. 

Problema este clasica : se cere un cuplaj bipartit maxim de cost minim. Asta se poate rezolva cu flux maxim de cost minim. Cauta un tutorial pe net. Din cate tin minte in Cormen nu e explicat. (totusi te-as sfatui ca prima data sa te uiti peste algortimii: Ford-Fulkerson si Bellman-Ford si dupa aia sa incerci sa-l implementezi).

Spor!

[•peanutz]

Mi-am dat si eu seama ca e bipartit..... si cam atat )
De vreo 2 zile tot incerc.... tot imi iasa pana la urma

Merci pentru sfat!!!

[•cos_min]

Construiesc un graf cu 2*n+1 noduri. Nodul sursa 0 si nodul destinatie 2*n+1. Capacitatiile in graf sunt 1 peste tot. Cost de la nodul i [1..n] pana la nodul j [n+1..2*n] este in matr citita c[i ][j-n]. Dupa care fac algoritmul de flux maxim de cost minim, si cam atat. Si la afisare adun costul nod de la n+1 ... 2*n.

Ii bine ce fac si probabil gresesc undeva la implementare ? Sau trebuie modificat ceva si in alg de flux maxim de cost minim?

[•cos_min]

deci ma poate ajuta cineva? 

[•vladcyb1]

Vezi sa ai grija sa pui cost negativ pe muchiile de intoarcere.

[•sima_cotizo]

Ok, toate bune si frumoase, dar pana la pasul 4. Nu am implementat algoritmul, dar am facut "de mana"...

Am ajuns la cazul in care avem copii 2 si 4 liberi si calculatoarele 1 si 5.
Copilul 4 face distanta 6 pana la oricare calculator, copilul 2 prefera sa se aseze la comp 1 ca e mai aproape. Dar bellman-ford (sau dijkstra) il poate aseza pe copilul 2 la comp 1 si se strica tot.
Eu nu inteleg chestia asta, ca pot exista exemple in care e invers, copilul 2 se aseaza la comp 5 ca e mai aproape...

  eu unul nu inteleg cum merge algoritmul asta, decat in mare... si complexitatea ajunge [dupa mine] la N^3, caz in care ar putea fi rezolvata cu un roy-floyd...  un pic de help, please! 

[•gurney]

    -din cate stiu bellman ford se face in O(n^3) de unde cea finala o(n^4).Cum ajung la o(n^3)total?

[•wefgef]

Incearca sa faci Bellman-Ford cu coada. In practica merge mult mai bine.

[•gurney]

    -Da, se pare ca se comporta mai bine. Mersi, bafta la oni. 

[•devilkind]

algoritmu ungar intra??? adik eu iau 20 de puncte si mi se pare destul de ciudat.  Am gresit eu la implementare si imi cicleaza undeva sau nu se incadreaza in timp. (iau 8 TLE-uri)

[•CezarMocan]

Eu cu ungaru am luat 100... 

[•domino]

Eu cu ungaru am luat 100... 

 
 Ungar nu e tocmai cel mai usor de implementat algoritm pentru asta. Folositi flux maxim de cost minim, fie cu Bellman Ford cu coada, fie cu Dijkstra.

[•vanila0406]

Da...si eu am luat 100 cu ungar...dar am gasit intro carte de o explicatie cu dijkstra...desi ungar mi se pare mult mai usor de inteles...chiar daca este foarte costisitor la implementare

[•Florian]

Cu back se poate lua mai mult de 10 puncte???