Flux2

[•savim]

Aici se pot pune întrebări legate de problema Flux2 de la Runda 3 a concursului Algoritmiada 2013.

Timpul alocat întrebărilor este de 1 ora dupa inceperea concursului. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII.

[•mugurelionut]

Pentru fiecare retea data, se garanteaza ca cantitatea de apa transportata de la S la D este maxim posibila ?

Altfel spus, trebuie DOAR sa verificam ca se obtine costul minim (in conditiile in care cantitatea de apa este maxima) ?

In cazul in care raspunsul la intrebarea precedenta este NU: trebuie sa verificam atat:
1) ca se transporta o cantitate maxima de apa de la S la D
SI
2) costul de transport al apei este minim
?

[•freak93]

NU.

[•Cristy94]

Cate teste sunt? Limitele lui T nu sunt precizate.

[•freak93]

T <= 6. Modific acum enunutul.

[•Cristy94]

"propune ca prin aceasta conducta sa treaca fi unitati de apa pe secunda"

Apa care trece prin conducta trece in sensul x->y ?

[•freak93]

DA

[•PlayLikeNeverB4]

Pot exista mai multe conducte intre doua rezervoare?

[•freak93]

NU

[•Cristy94]

Pentru fiecare retea data facem o data algoritmul de flux (cautam drumul de ameliorare de cost minim) si daca exista inseamna ca raspunsul pentru acel test este 0.
Imi da ba TLE (daca initializez de fiecare data matricile ce le folosesc) ba WA ... Asta era ideea de rezolvare?

[•mugurelionut]

Exista 2 cazuri cand raspunsul pe un test e 0:

1) daca fluxul mai poate fi crescut cu cel putin 1 unitate (in acest caz nu ai nevoie sa folosesti si costurile : o simpla parcurgere de la S catre D e suficienta, tinand cont ca e posibil ca pt a incrementa fluxul global sa fie nevoie sa-l decrementezi pe unele muchii ; anyway, e practic o iteratie dintr-un algoritm de flux maxim fara costuri)

2) daca fluxul nu mai poate fi crescut, dar exista un ciclu de cost negativ in reteaua data (adica costul ar putea fi redus) Pentru a determina daca exista ciclu de cost negativ, fiecare muchie x->y de cost C se transforma in maxim 2 muchii :
-- muchie x->y de cost C daca flux(x->y) < capacitate(x->y)
-- muchie y->x de cost -C  daca flux(x->y) > 0

Cazul 2 e cazul mai greu, deoarece are complexitatea mai mare: teoretic se poate ajunge la O(N^3) sau O(N*(N+M)) folosind algoritmul Bellman-Ford sau Bellmand-Ford-Moore (practic Bellmand-Ford dar cu coada). Eu am implementat destul de eficient algoritmul asta (desi, aparent, ultima versiune submitata nu era cea mai rapida si eram aproape sa iau TLE pe unul din teste).

Sunt curios daca exista o solutie de complexitate (teoretica) mai buna.

[•wefgef]

Exista 2 cazuri cand raspunsul pe un test e 0:

1) daca fluxul mai poate fi crescut cu cel putin 1 unitate (in acest caz nu ai nevoie sa folosesti si costurile : o simpla parcurgere de la S catre D e suficienta, tinand cont ca e posibil ca pt a incrementa fluxul global sa fie nevoie sa-l decrementezi pe unele muchii ; anyway, e practic o iteratie dintr-un algoritm de flux maxim fara costuri)

2) daca fluxul nu mai poate fi crescut, dar exista un ciclu de cost negativ in reteaua data (adica costul ar putea fi redus) Pentru a determina daca exista ciclu de cost negativ, fiecare muchie x->y de cost C se transforma in maxim 2 muchii :
-- muchie x->y de cost C daca flux(x->y) < capacitate(x->y)
-- muchie y->x de cost -C  daca flux(x->y) > 0

Cazul 2 e cazul mai greu, deoarece are complexitatea mai mare: teoretic se poate ajunge la O(N^3) sau O(N*(N+M)) folosind algoritmul Bellman-Ford sau Bellmand-Ford-Moore (practic Bellmand-Ford dar cu coada). Eu am implementat destul de eficient algoritmul asta (desi, aparent, ultima versiune submitata nu era cea mai rapida si eram aproape sa iau TLE pe unul din teste).

Sunt curios daca exista o solutie de complexitate (teoretica) mai buna.

Aceasta este si solutia oficiala. Felicitari, Mugurel!

[•ctlin04]

Spuneti-mi va rog unde gresesc  
Am incercat sa fac in felul urmator:
pentru o muchie x y si x1-fluxul propus de angajat, y1-fluxul maxim pe muchie, adaug
cost [ x ] [ y ]-costul de intretinere; cost [ y ] [ x ]=-cost [ x ][ y ];
capacitate [ y] [ x]=x1; capacitate  [ x] [ y]=y1-x1;
acum pot merge pe o muchie doar daca capcitate [ x][ y]>0;
Dupa ce mi-am format graful in acest fel fac un dfs din sursa sa vad daca pot ajunge la destinatie, daca ajung rezulta ca voi putea mari fluxul cu capacitatea minima de pe drum, respectiv in acest caz consider planul angajatului gresit.
Daca nu am ajuns la destinatie controlez daca exista ciclu de cost negativ cu Bellman Ford, daca exista iarasi consider planul gresit, daca nu atunci planul este corect.
Iau incorect.