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
Fie un graf orientat cu N noduri si M muchii. V este multimea nodurilor din graf, iar E multimea muchiilor. Asociem fiecarei muchii (u,v) o capacitate nenegativa cap(u,v). Consideram doua varfuri speciale: nodul 1 care va fi denumit sursa si nodul N, denumit destinatie. Orice nod i (2 ≤ i ≤ N-1) se gaseste pe cel putin un drum de la 1 la N. Definim fluxul in graf ca fiind o functie f: E -> Z. Functia f satisface urmatoarele conditii:
- este restrictionata de capacitate, adica ∀ ( i, j) ∈ E avem f(i,j) ≤ cap(i,j)
- fluxul se conserva, adica ∀ i ∈ V valoarea fluxului care intra in nodul respectiv este egala cu valoarea fluxlui care iese din nodul respectiv (∀ i ∈ V avem ca
, unde E este multimea muchiilor grafului)
Valoarea fluxului este 
, adica fluxul total care pleaca din nodul sursa.
Cerinta
Se cere sa se determine valorile functiei f pentru fiecare muchie (i,j) astfel incat valoarea fluxului sa fie maxima.
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, semnificand faptul ca exista muchie de la nodul a la nodul b avand capacitatea c.
Date de iesire
In fisierul de iesire flux1.out se va scrie fluxul maxim.
Restrictii
- 1 ≤ N ≤ 200
- 1 ≤ N ≤ 19900
- capacitatea fiecarei tevi este un numar natural nenul mai mic sau egal cu 10 000 000.
- daca in fisier exista muchia (a, b), cu siguranta nu va exista si muchia (b,a)
- fluxul maxim va fi ≤ 2 000 000 000
Exemplu
| flux1.in | flux1.out |
|---|---|
| 6 12 1 2 6 1 3 3 3 4 5 4 5 4 5 6 4 3 6 100 2 4 3 1 5 4 1 3 6 4 6 5 2 3 5 3 6 4 | 13 |
Indicatii de rezolvare
Problema se rezolva cu ajutorul algoritmului Ford Fulkerson, care are urmatorii pasi.
- se cauta un drum de la sursa (in cazul nostru, nodul 1) la destinatie (in cazul nostru N) cu orice algoritm (bfs, dfs, etc.).
- de pe acest drum se alege muchia de capacitate minima (fie ea i)
- din fiecare muchie a drumului ales se scade capacitatea c~i~ (astfel muchia i va avea capacitatea 0 si poate fi ignorata la urmatorii pasi)
- se creste fluxul cu c~i~ si se repeta de la pasul 1
- algoritmul se repeta de la pasul 1
Feedback Cosmin: pune n mare sa se poata implementa si dinic. Ar trebui ceruta eventual si taietura minima, ca multi nu stiu gasi taietura dupa ce au determinat fluxul maxim.
Probleme asemanatoare
infoarena - Trafic
