| 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 veţi afişa un singur număr, reprezentând numărul de muchii ale grafului care fac parte din cel puţin un ciclu de cost zero.
Restricţii
- 1 ≤ N ≤ 2000
- 0 ≤ M ≤ 15 000
- Costul unei muchii este un număr întreg între -10 000 si +10 000.
- Pot exista mai multe muchii între aceeaşi pereche de noduri, eventual chiar şi orientate în acelaşi sens (şi putând avea costuri diferite).
Exemplu
| zeroc.in | zeroc.out |
|---|---|
| 6 8 1 2 -2 2 3 6 3 4 -2 4 1 -2 4 5 -7 5 2 7 5 6 3 6 1 8 | 4 |
Explicaţie
Singurele muchii care aparţin unui ciclu de cost zero sunt primele 4 muchii din fişier.
