Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | zeroc.in, zeroc.out | Sursă | Lot Cluj 2009, Baraj 6 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Sima Cotizo •sima_cotizo |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Zeroc
Se dă un graf orientat cu N noduri (numerotate de la 1 la N) şi M muchii (numerotate de la 1 la M). Fiecare muchie i (1≤i≤M) este orientată de la ai la bi şi are un cost ci (pozitiv, zero sau negativ). Un ciclu este o secvenţă de muchii distincte mu(1), mu(2), ..., mu(q), astfel încât bmu(i)=amu(i+1) (1≤i≤q-1) şi bmu(q)=amu(1). Costul unui ciclu este egal cu suma costurilor muchiilor ce formează ciclul.
Cerinţă
Ştiind că nu există cicluri de cost negativ în graf, determinaţi câte dintre cele M muchii ale grafului fac parte din cel puţin un ciclu de cost zero.
Date de intrare
Pe prima linie a fişierului de intrare zeroc.in se află numerele naturale N şi M, separate printr-un spaţiu. Pe a i-a linie din următoarele M linii se află câte 3 numere întregi, ai, bi, şi ci, separate prin câte un spaţiu şi având semnificaţia că există o muchie orientată de la nodul ai la nodul bi, având costul ci.
Date de ieşire
În fişierul de ieşire zeroc.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| zeroc.in | zeroc.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
