Fişierul intrare/ieşire:zeroc.in, zeroc.outSursăLot Cluj 2009, Baraj 6
AutorMugurel Ionut AndreicaAdăugată desima_cotizoSima Cotizo sima_cotizo
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.inzeroc.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content