critice

Critice

== include(page="template/taskheader" task_id="critice") ==

==Include(page="template/taskheader" task_id="critice")==

Poveste ...

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. Restrictii

h2. 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$.

h2. Date de intrare

h2. 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.

h2. Date de iesire

h2. 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$

h2. Exemplu

| critice.in | critice.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. critice.in |_. critice.out |
| 5 6
2 1 2
2 3 3
3 5 4
1 4 7
4 3 2
4 5 6
| 2
1
4 |

== include(page="template/taskfooter" task_id="critice") ==

==Include(page="template/taskfooter" task_id="critice")==
 
 

306