critice

Critice

== include(page="template/taskheader" task_id="critice") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| critice.in | critice.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="critice") ==

==Include(page="template/taskheader" task_id="critice")==
==Include(page="template/raw")==
 
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.
 
h2. Cerinta
 
Fiind data reteaua din pivnita lui Algorel determinati tunelele critice.
 
h2. Date de Intrare (fisier: critice.in)
 
Pe prima linie 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.
 
h2. Date de Iesire (fisier: critice.out)
 
Prima linie a fisierului de iesire 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.
 
h2. Restrictii
 
S 1 <= N <= 1.000
 
S 1 <= M <= 10.000
 
S Rezistentele sunt numere naturale mai mici sau egale cu 10.000
 
S Intre oricare doua noduri exista cel mult un tunel
 
S Orice tunel poate fi parcurs in ambele sensuri
 
S Petru 50% din teste M <= 1.000
 
h2. Exemplu
 
critice.in critice.out
5 6 2
 
2 1 2 1
 
2 3 3 4
 
3 5 4
 
1 4 7
 
4 3 2
 
4 5 6
 
 
==Include(page="template/taskfooter" task_id="critice")==