| Fişierul intrare/ieşire: | tarnacop.in, tarnacop.out | Sursă | Algoritmiada 2012, Runda Finala |
| Autor | Cosmin Gheorghe | Adăugată de |  Serban Andrei Stan •savim |
| Timp execuţie pe test | 1 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | tarnacop.out |
|---|---|
| 4 4 1 4 1 2 1 1 2 3 1 1 3 4 1 1 2 4 2 0 | 1 1 2 |
