|
Titlul: 522 Renovare Scris de: Adrian Diaconu din Septembrie 11, 2007, 14:20:18 Aici puteţi discuta despre problema Renovare (http://infoarena.ro/problema/renovare).
Titlul: Răspuns: 522 Renovare Scris de: Ionescu Vlad din Septembrie 12, 2007, 16:04:13 Am o intrebare... in solutia oficiala zice:
Citat 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? Titlul: Răspuns: 522 Renovare Scris de: Andrei Homorodean din Septembrie 12, 2007, 16:15:55 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 :))
Titlul: Răspuns: 522 Renovare Scris de: Ionescu Vlad din Septembrie 13, 2007, 01:23:50 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? ](*,)
Titlul: Răspuns: 522 Renovare Scris de: Savin Tiberiu din Septembrie 13, 2007, 09:03:08 tii 2 matrici. Una ptr muchii cu cost si una ptr muchii fara cost ;).
Titlul: Răspuns: 522 Renovare Scris de: Sima Cotizo din Septembrie 16, 2007, 11:44:48 Cat va da pentru :
Cod: 6 8 11 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... Titlul: Răspuns: 522 Renovare Scris de: Ionescu Vlad din Septembrie 16, 2007, 12:31:58 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...
Titlul: Răspuns: 522 Renovare Scris de: Adrian Diaconu din Septembrie 16, 2007, 15:08:19 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
Titlul: Răspuns: 522 Renovare Scris de: Chis Raoul din Septembrie 16, 2007, 17:01:48 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 ... ](*,)
Titlul: Răspuns: 522 Renovare Scris de: Ionescu Vlad din Septembrie 16, 2007, 17:33:56 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... Titlul: Răspuns: 522 Renovare Scris de: Paul-Dan Baltescu din Septembrie 16, 2007, 18:36:10 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. :) Titlul: Răspuns: 522 Renovare Scris de: Sima Cotizo din Septembrie 17, 2007, 07:06:34 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? Titlul: Răspuns: 522 Renovare Scris de: Dragos Oprica din Aprilie 05, 2010, 09:57:34 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? :) |