== include(page="template/taskheader" task_id="flux2") ==
Poveste şi cerinţă...
De curand primarul Infoarena a angajat pe cineva sa se ocupe de reteaua de transport a apei din oras. Ea poate fi reprezentata prin $N$ rezervoare si $M$ conducte care unesc fiecare $2$ rezervoare distincte. Dintre aceste $N$ rezervoare $doua$ sunt mai speciale, $S$ si $D$. Rezervorul principal (cel din care apa intra in reteaua de transport) este cel cu indicele $S$, iar prin rezervorul cu indicele $D$ apa ajunge in oras. In toate celelalte rezervoare cantitatea de apa care intra este egala cu cea care iese (nu ar avea sens sa iasa mai multa apa si daca ar intra mai multa rezervorul ar exploda la un moment dat). Apa circula in retea doar prin cele $M$ conducte si pentru fiecare conducta in parte se cunoaste un pret $dis{~i~}$ care indica ce pret de intretinere trebuie sa plateasca primaria pentru a transporta prin acea conducta o unitate de apa pe secunda. Deasemenea pentru fiecare conducta se mai cunoaste si ce cantitate de apa poate trece maxim prin ea intr-o secunda.
Persoana angajata sa se ocupe de aceasta retea a fost insarcinata sa trimita cat mai multa apa de la $S$ la $D$, dar in acelasi timp sa aiba grija sa fie un cost minim in fiecare secunda (evident costul e acelasi pentru fiecare secunda). Intrucat primaria Infoarena e ocupata cu multe lucruri va roaga pe voi sa va uitati pe cateva planuri de-ale angajatului (pentru mai multe retele de transport al apei) si sa spuneti pentru fiecare daca este eficient sau nu.
In schimb primaria Infoarena va garanteaza 100 de puncte la aceasta problema.
h2. Date de intrare
Fişierul de intrare $flux2.in$ ...
Fişierul de intrare $flux2.in$ va contine pe prima linie un numar natural $T$ reprezentand numarul de retele de transport (respectiv de planuri de-ale angajatului).
Fiecare retea de transport este apoi descrisa in felul urmator:
* Pe prima linia 4 numere naturale $N$, $M$, $S$ si $D$ reprezentand numarul de rezervoare, numarul de conducte, rezervorul sursa si respectiv cel destinatie.
* Urmatoarele $M$ linii vor contine fiecare $5$ numere fiecare $x{~i~}$, $y{~i~}$, $dis{~i~}$, $f{~i~}$ si ${~i~}c$ reprezentand o conducta care pleaca din $x{~i~}$ spre $y{~i~}$ ce are costul de intretinere $dis{~i~}$ si cantitatea maxima de apa care poate trece prin ea intr-o secunda fiind $c{~i~}$. Deasemenea stiti ca recentul angajat al primariei propune ca prin aceasta conducta sa treaca $f{~i~}$ unitati de apa pe secunda.
h2. Date de ieşire
În fişierul de ieşire $flux2.out$ ...
În fişierul de ieşire $flux2.out$ trebuie sa se afle $T$ linii, fiecare avand raspunsul la respectiva retea de transport.
Astfe pe linia $i$ se va afla $1$ daca planul propus de angajat este eficient (obtine cel mai mic cost posibil pentru cantitatea maxima de apa) sau $0$ in caz contrar.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 6$
* $2 ≤ N ≤ 1.000$
* $0 ≤ M ≤ 200.000$
* $1 ≤ S, D, x{~i~}, y{~i~} ≤ N$ si $S ≠ D$
* $0 ≤ f{~i~}, c{~i~} ≤ 1.000.000$
* $0 ≤ dis{~i~} ≤ 1.000$
* Planul propus de angajat este corect (respecta restrictiile din enunt, mai exact cantitatea de apa care intra intr-un rezervor este egala cu cea care iese mai putin pentru $S$ si $D$)
h2. Exemplu
table(example). |_. flux2.in |_. flux2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
4 5 3 4
2 1 0 4 4
2 4 1 4 4
3 2 0 8 8
3 4 2 2 2
1 4 4 4 4
4 6 1 4
1 2 1 0 1
2 3 0 0 2
4 2 2 0 4
1 3 2 6 6
3 4 0 6 6
4 1 4 0 3
|1
0
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="flux2") ==
== include(page="template/taskfooter" task_id="flux2") ==
