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\{1,N} valoarea fluxului care intra in nodul respectiv este egala cu valoarea fluxlui care iese din nodul respectiv (∀ i ∈ V avem
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 ≤ M ≤ N*(N-1)
- capacitatea fiecarei muchii este un numar natural nenul mai mic sau egal cu 10 000 000.
- daca, in fisierul de intrare, exista muchia (a,b) poate sa existe 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 capi (astfel muchia i va avea capacitatea 0 si poate fi ignorata la urmatorii pasi)
- se creste fluxul cu capi
- algoritmul se repeta de la pasul 1