Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | flux1.in, flux1.out | Sursă | |
| Autor | Autor necunoscut | Adăugată de |  Bogdan-Alexandru Stoica •fireatmyself |
| Timp execuţie pe test | 1.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Flux Maxim
Se ne imaginam o retea formata din M tevi. Lichidul pe o teava se scurge intr-un anumit sens, iar fiecare teava are un anumit diametru, deci prin aceasta nu poate trece mai mult lichid decat o cantitate limita (specifica fiecarei tevi). Tevile sunt conectate intre ele prin jonctiuni numerotate de la 1 la N. Jonctiunea 1 este legata la un robinet, iar jonctiunea N este legata la o scurgere. In afara de acestea doua, lichidul nu se poate acumula in nico alta jonctiune (cantitatea de lichid care intra trebuie sa fie egala cu cea care iese).
Se cere sa se determine cantitatea totala maxima de apa ce poate trece de la la robinet la scurgere.
Reteaua se va da sub forma unui graf orientat cu N noduri (jonctiunile) si M muchii (tevile), fiecare muhcie avand o anumita capacitate (debitul).
Date de intrare
Pe prima linie a fisierul de intrare flux1.in se afla N si M. Urmeaza apoi M linii ce contin 3 numere naturale a, b si c. Linia i+1 semnifica faptul ca teava respectiva este marginita de jonctiunile a si b, apa se scurge de la a spre b, iar debitul acesteia este c.
Date de iesire
In fisierul de iesire flux1.out se va scrie cantitatea totala maxima de apa ce poate trece de la la robinet la scurgere
h2. Restrictii
- 1 ≤ N ≤ 200
- 1 ≤ N ≤ 19 900
- capacitatea fiecarei tevi este un numar natural nenul mai mic sau egal cu 150.
- fluxul maxim va fi ≤ 2 000 000 000
Exemplu
| flux1.in | flux1.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
