522 Renovare

[•DITzoneC]

Aici puteţi discuta despre problema Renovare.

[•Dastas]

Am o intrebare... in solutia oficiala zice:

pentru fiecare muchie a b c cst cu semnificatia din enunt vom adauga 2 muchii in retea, una de capacitate c si cost 0 si inca una de capacitate infinit si cost cst.

Asta inseamna ca intre fiecare doua noduri din graf intre care exista muchie data, reteaua nou formata va avea doua muchii? (una de cost 0 si capacitate c si cealalta de cost cst si capacitate infinit).

De exemplu, daca am muchia 1 2 3 2
Voi memora muchiile 1 2 3 0 si 1 2 inf 2?

[•peanutz]

Da, asa e. Dar cand faci flux si treci printr-o muchie cu cost diferit de 0, tre sa adaugi la costul total capacitate_folosita*cst. (Poate e in plus, dar sa fiu sigur ca ai inteles )

[•Dastas]

Mersi, am inteles. Totusi, nu prea inteleg cum faci flux intr-un graf in care ai doua muchii intre doua noduri x si y. Ma cam zapaceste la fazele de genul f[ i][j] = fluxul trimis pe i,j, la reconstituirea drumului de cost minim etc... Cam cum ar trebui facuta implementarea?

[•devilkind]

tii 2 matrici. Una ptr muchii cu cost si una ptr muchii fara cost .

[•sima_cotizo]

Cat va da pentru :

Cod:

6 8 11
1 2 3 4
1 4 4 2
2 3 2 3
2 5 3 4
4 5 4 4
5 6 6 8
3 6 4 5
3 5 2 3

Mie imi da 30... nu prea stiu de ce iau 9*incorect  am facut ore de debug si imi pare corect... tot ce fac este un ford-fulkerson cu bellman-ford modificat ca sa rezolv problema cu costurile...

[•Dastas]

30 cu o solutie care ia 90 + un TLE. Chiar, testul 9 se poate trece cu o implementare pe matrice de adiacenta? Sau trebuie liste? Cu liste inca nu iau decat 20...

[•DITzoneC]

Eu am luat 100 si cu matrice de adiacenta desi cam la limita. Sursa cu liste insa imi ruleaza mult mai repede sub 0.5

[•raula_san]

Mda, si mie imi da tot 30, pe o sursa de 20p (8 * Wa) ... Am stat si eu ca si Coty ore la debug + ca am scris vreo 6 sau 7 surse ... 

[•Dastas]

Si cu liste cam cum s-ar face? Eu am facut cu liste si iau doar 20, iar pe aceeasi idee, cu matrice, iau 90 + TLE...

Ideea mea e sa dublez nodurile, a.i. daca am muchie de la x la y, bag doua muchii, una de la x la y+n+1 iar alta de la y+n+1 la y, una cu cost cst si flux infinit, cealalta cu cost 0 si flux infinit. Plus de la x la y direct de cost 0 si flux c. Cum am zis, pe matrice ia 90, pe liste (vector din stl de fapt) intra lejer in timp dar nu ia decat 20. Nu pot sa-mi dau seama ce are si am testat si verificat ore intregi...

[•pauldb]

O implementare lejera e sa tii doar muchiile, iar pentru noduri liste (vectori STL) cu muchiile cu un capat in nodul respectiv.

Se pare ca a prins bine un flux la Warmup.

[•sima_cotizo]

Eu unul nu am nicio lista de noduri, nu vad la ce mi-ar folosi... am doar vectorul de muchii pentru bellman-ford... si intra lejer in timp.

Bine, m-am gandit ca pot face flux normal, cu bf (pentru care e buna lista) si sa fac apoi si partea de costuri, dar cred ca merge si varianta mea... in procedura de bellman, pentru o muchie (x,y) am doua cazuri, daca am saturat-o si cost(y)>cost(x) atunci cost(y)=cost(x)+cost_muchie, altfel (nu e saturata) daca cost(y)>cost(x) atunci cost(y)=cost(x) ... am gresit ceva? 

PS: nu am considerat si muchia inversa (partea in care scazi flux pe muchia inversa) pentru ca am zis ca tevile alea sunt cam orientate... iar cand am bagat si conditiile pt. chestia asta mi s-a cam dat peste cap programul... de la asta sa fie?

[•DraStiK]

Ma ajuta cineva și pe mine cu o explicație?

Când fac Flux Maxim de Cost Minim, și am o muchie de la x->y de cost cst, în graf, normal trebuie sa adaug și o muchie de la y->x de cost -cst.

Dar aici, dacă nu am mai adăugat muchia inversa, am scăpat de TLE și surpriza, am luat 100p. De ce e asa?