Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | maxflow.in, maxflow.out | Sursă | Arhiva educationala |
| Autor | Arhiva Educationala | Adăugată de |  Savin Tiberiu •devilkind |
| Timp execuţie pe test | 0.03 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Flux maxim
O retea de transport este un graf orientat in care fiecare muchie are asociata o anumita capacitate si o anumita cantitatea de flux. Fluxul primit de fiecare muchie trebuie sa fie mai mic sau egal decat capacitatea acesteia. De asemenea pentru fiecare nod fluxul care intra in nod trebuie sa fie egal cu fluxul care iesa. Cu alte cuvinte, suma fluxulurilor asociate muchiilor care intra intr-un nod trebuie sa fie egala cu suma fluxurilor asociate muchiilor care iesa din nod, exceptie facand nodurile speciale S si D, denumite sursa respectiv destinatie. Din sursa poate iesi flux fara sa intre iar in destinatie poate intra flux fara sa iasa. Valoarea fluxului unei astfel retele este egal cu suma fluxului care iesa din sursa sau suma fluxului care intra in destinatie.
Cerinta
Dandu-se o retea de transport, in care initial fluxul pe fiecare muchie este 0, sa se calculeze fluxul maxim care poate fi trimis prin aceasta.
Date de intrare
Fisierul de intrare maxflow.in va contine pe prima linie 2 numere, N si M, reprezentand numarul de noduri respectiv numarul de muchii. Pe urmatoarele M linii se vor afla cate 3 numere, x, y si z insemnand ca exista o muchie care pleaca de la nodul x, ajunge in nodul y si are capacitatea z.
Date de ieşire
In fisierul de iesire maxflow.out se va afla un singur numar F reprezentand fluxul maxim ce poate fi trimis prin retea.
Restricţii
- 2 ≤ N ≤ 300
- 1 ≤ M ≤ 1 000
- Nodul 1 este nodul sursa, iar nodul N este nodul destinatie
Exemplu
| maxflow.in | maxflow.out |
|---|---|
| 4 5 1 2 3 1 3 5 2 4 6 3 4 4 3 2 3 | 8 |
Explicaţie
Fluxul maxim care poate fi trimis din sursa catre destinatie este 8 si este trimis astfel:
In figura de mai sus, fiecare muchie are asociate 2 numere reprezentand fluxul si capacitatea asociate muchiei respective.
