Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | flux.in, flux.out | Sursă | Summer Challenge 2007, runda 1 |
| Autor | Din Folclor | Adăugată de |  Adrian Diaconu •DITzoneC |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Flux
In oras exista N rezervoare legate intre ele prin M conducte. Rezervorul cu numarul 1 este sursa, iar rezervorul cu numarul N este destinatia. Pentru fiecare conducta se cunoaste volumul de apa care poate trece prin ea. Pentru fiecare rezervor se stie ca volumul de apa care intra in respectivul rezervor este egal cu volumul de apa care iese din respectivul rezervor (lucru care nu este valabil pentru sursa si destinatie).
In plus se mai impune urmatoarea restrictie: pentru oricare doua rezervoare i si j suma volumelor de apa ce trec prin conductele unui drum arbitrar de la i la j este constanta.
Cerinta
Calculati volumul maxim de apa care poate ajunge la destinatie intr-o astfel de retea.
Date de intrare
In fisierul de intrare flux.in se afla pe prima linie N, numarul de rezervoare. Pe a doua linie se afla M, numarul de conducte. Urmeaza apoi M linii pe care se afla triplete a b c cu semnificatia ca exista o conducta de capacitate c intre a si b.
Date de iesire
Fisierul de iesire flux.out va contine o singura linie pe care se afla volum maxim de apa care poate ajunge la destinatie.
Restrictii
- {$2 ≤ N ≤ 100}
- {$1 ≤ M ≤ 5.000}
- {$1 ≤ c ≤ 10.000}
- Pentru rezultat se accepta o eroare de 10-3
Exemplu
| flux.in | flux.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
