Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2013-02-24 07:16:12.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:flux2.in, flux2.outSursăAlgoritmiada 2013, Runda 3
AutorAndrei GrigoreanAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.7 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Flux2

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 disi 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.

Date de intrare

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 xi, yi, disi, fi si ic reprezentand o conducta care pleaca din xi spre yi ce are costul de intretinere disi si cantitatea maxima de apa care poate trece prin ea intr-o secunda fiind ci. Deasemenea stiti ca recentul angajat al primariei propune ca prin aceasta conducta sa treaca fi unitati de apa pe secunda.

Date de ieşire

Î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.

Restricţii

  • 1 ≤ T ≤ 6
  • 2 ≤ N ≤ 1.000
  • 0 ≤ M ≤ 200.000
  • 1 ≤ S, D, xi, yi ≤ N si S ≠ D
  • 0 ≤ fi, ci ≤ 1.000.000
  • 0 ≤ disi ≤ 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)

Exemplu

flux2.influx2.out
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?