Fişierul intrare/ieşire:critice.in, critice.outSursăpreONI 2005 Runda 3
AutorSilviu-Ionut GanceanuAdăugată de
Timp execuţie pe test0.125 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Critice

Algorel are in pivnita o retea subterana prin care misuna sobolani. Reteau consta din N adaposturi numerotate de la 1 la N si M tunele intre acestea. Adaposturile 1 si N comunica cu suprafata fiind singurele locuri din retea cu aceasta propietate (nici un alt adapost sau tunel nu mai are iesire la suprafata). Algorel vrea sa trimita un numar maxim de pisici in retea. Pisicile intra prin adapostul 1 si ies prin adapostul N. Nici o pisica nu poate ramane in retea. Pentru fiecare tunel se stie rezistenta lui, adica numarul maxim de pisici care pot trece prin el fara ca sa se darame. Daca printr-un tunel cu rezistenta nenula a trecut o pisica atunci rezistenta acestuia scade cu o unitate. Algorel a observat ca exista anumite tunele care au propietatea ca daca rezistenta lor creste in timp ce rezistenta celorlalte tunele ramane la fel atunci va creste si numarul maxim de pisici pe care le poate trimite prin retea. El a denumit tunelele cu aceastra propietate tunele critice.

Cerinta

Fiind data reteaua din pivnita lui Algorel determinati tunelele critice.

Date de Intrare

Pe prima linie a fisierului critice.in se gasesc numerele naturale N si M reprezentand numarul de adaposturi si numarul de tunele din reteaua subterana. Urmeaza M linii continand trei numere naturale separate prin spatii, A B C, cu semnificatia: intre adaposturile A si B (A != B) exista un tunel cu rezistenta C.

Date de Iesire

Prima linie a fisierului de iesire critice.out contine un numar natural K reprezentand numarul de tunele critice din reteaua lui Algorel. Urmatoarele K linii contin cate un numar natural reprezentand indicii muchiilor critice. Indicii vor fi sortati crescator. Muchiile sunt numerotate de la 1 la M dupa ordinea din fisierul de intrare.

Restrictii

  • 1 ≤ N ≤ 1000
  • 1 ≤ M ≤ 10000
  • Rezistentele sunt numere naturale mai mici sau egale cu 10000
  • Intre oricare doua noduri exista cel mult un tunel
  • Orice tunel poate fi parcurs in ambele sensuri
  • Petru 50% din teste M <= 1000

Exemplu

critice.incritice.out
5 6
2 1 2
2 3 3
3 5 4
1 4 7
4 3 2
4 5 6
2
1
4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content