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: VxV -> Z. Functia f satisface urmatoarele conditii:
- este restrictionata de capacitate, adica ∀ i, j ∈ V avem f(i,j) ≤ cap(i,j)
- este antisimetrica, adica ∀ i, j ∈ V avem f(i,j) = -f(j,i)
- 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.) si fie acesta 1 -> i1 -> i2 -> ... -> ik -> N
- de pe acest drum se alege muchia pentru care valoarea cap(i,j)-f(i,j) este minima (fie ea cmin)
- se cresc cu cmin f(1,i1), f(i1,i2), ..., f(ik,N) si se scad cu cmin f(i1,1), f(i2,i1), ..., f(N,ik)
- se creste valoarea fluxul total cu cmin
- algoritmul se repeta de la pasul 1
O descriere detaliata a algoritmului o gasiti aici.
