== include(page="template/taskheader" task_id="zeroc") ==
Poveste şi cerinţă...
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 $a{~i~}$ la $b{~i~}$ şi are un cost $c{~i~}$ (pozitiv, zero sau negativ). Un ciclu este o secvenţă de muchii distincte $mu(1), mu(2), ..., mu(q)$, astfel încât $b{~mu(i)~} = a{~mu(i+1)~}$ $(1 ≤ i ≤ q-1)$ şi $b{~mu(q)~} = a{~mu(1)~}$. Costul unui ciclu este egal cu suma costurilor muchiilor ce formează ciclul.
h2. 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.
h2. Date de intrare
Fişierul de intrare $zeroc.in$ ...
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, $a{~i~}$, $b{~i~}$, şi $c{~i~}$, separate prin câte un spaţiu şi având semnificaţia că există o muchie orientată de la nodul $a{~i~}$ la nodul $b{~i~}$, având costul $c{~i~}$.
h2. Date de ieşire
În fişierul de ieşire $zeroc.out$ ...
Î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.
h2. 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).
h2. Exemplu
table(example). |_. zeroc.in |_. zeroc.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
h3. Explicaţie
...
Singurele muchii care aparţin unui ciclu de cost zero sunt primele 4 muchii din fişier.
== include(page="template/taskfooter" task_id="zeroc") ==
