Fişierul intrare/ieşire:tarnacop.in, tarnacop.outSursăAlgoritmiada 2012, Runda Finala
AutorCosmin GheorgheAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test1 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Tarnacop

Datorita sapaturilor excesive, galeriile miniere ale orasului Targu Mures au fost inundate de un rau subteran. Galeriile miniere pot fi considerate ca un graf cu N noduri (N camere) si M muchii (M coridoare intre camere). Se stie camera unde s-a produs accidentul (pe unde intra raul subteran in galerii), o vom nota pe aceasta cu S. Giugudel a venit in ajutorul minerilor impreuna cu tarnacopul sau magic. El a reusit astfel sa sape o gura de scurgere pentru apa din galerii, gura de scurgere aflandu-se in camera D. Acum, Giugudel stie pentru fiecare coridor capacitatea (numarul de metri cubi de apa ce pot trece intr-o secunda prin acel coridor) si cantitatea de apa ce trece prin acel coridor. Evident, aceasta cantitate va fi mai mica decat capacitatea. Giugudel stie numarul de metri cubi de apa ce se scurg in fiecare secunda prin camera D, si este curios sa afle pentru fiecare coridor, daca i-ar scadea capactitatea cu o unitate, daca ar scadea si capacitatea de apa ce se scurge in fiecare secunda prin camera D.

Date de intrare

Fişierul de intrare tarnacop.in, va contine pe prima linie numerele N,M,S,D cu semnificatia din enunt. Pe fiecare dintre urmatoarele M linii se va gasi cate un cvadruplet de forma X,Y,C,I, cu semnificatia ca exista un coridor intre camerele X si Y, de capacitate C, prin care trec in fiecare secunda I m3 de apa.

Date de ieşire

Fişierul de ieşire tarnacop.out va contine pe prima linie un numar natural K, reprezentand numarul muchiilor cu proprietatea ceruta in enunt. Pe fiecare dintre urmatoarele K linii se va gasi cate o pereche de numere natural X,Y, reprezentand faptul ca muchia de la X la Y are proprietatea din enunt. Muchiile trebuie afisate crescator dupa X, si in caz de egalitate, crescator dupa Y.

Restricţii

  • 1 ≤ S, D ≤ N ≤ 100 000
  • 1 ≤ M ≤ 300 000
  • S ≠ D
  • 0 ≤ I ≤ C ≤ 5 000 000
  • Muchiile de capacitate 0 nu pot fi micsorate
  • Pentru orice camera diferita de S si D, suma cantitatilor de apa care intra in camera este egala cu suma cantitatilor de apa care ies.
  • Apa poate curge pe un coridor doar in directia precizata in input (pentru o muchie X,Y apa va curge tot timpul dinspre X spre Y)
  • Cantitatea de apa ce se scurge prin D este maxim posibila
  • Nu vor exista mai multe muchii intre doua noduri
  • Nu va exista o muchie de la un nod la el insusi

Exemplu

tarnacop.intarnacop.out
4 4 1 4
1 2 1 1
2 3 1 1
3 4 1 1
2 4 2 0
1
1 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content