Fişierul intrare/ieşire:flux1.in, flux1.outSursă
AutorAutor necunoscutAdăugată defireatmyselfBogdan-Alexandru Stoica •fireatmyself
Timp execuţie pe test1.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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 S care va fi denumit sursa si nodul D, denumit destinatie (1 ≤ S,D ≤ N). Orice nod i (1 ≤ i ≤ N) se gaseste pe cel putin un drum de la S la D. Definim fluxul in graf ca fiind o functie f: VxV -> Z. Functia f satisface urmatoarele conditii:

  1. este restrictionata de capacitate, adica ∀ i, j ∈ V avem f(i,j) ≤ cap(i,j)
  2. este antisimetrica, adica ∀ i, j ∈ V avem f(i,j) = -f(j,i)
  3. ∀ i ∈ V avem \sum_{j \in V}^{} f(i,j) = 0

Valoarea fluxului este F = \sum_{(S,i) \in E}^{} f(S,i), adica fluxul total care pleaca din nodul sursa.

Cerinta

Se cere sa se determine valoarea maxima a fluxlui.

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 ≤ 2000
  • pentru 50% din teste 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 exista muchia (a,b) in fisierul de intrare, poate sa existe si muchia (b,a)
  • fluxul maxim va fi ≤ 2 000 000 000

Exemplu

flux1.influx1.out
6 12
4 3
1 3 5
1 5 4
2 1 3
2 6 5
4 2 6
4 3 3
4 5 4
4 6 6
5 3 4
6 1 5
6 2 4
6 3 100
19

Indicatii de rezolvare

Solutia de 50 de puncte

Problema se rezolva cu ajutorul algoritmului Ford Fulkerson, care are urmatorii pasi.

  1. se cauta un drum de la sursa la destinatie (fie acesta 1 -> i1 -> i2 -> ... -> ik -> N) cu proprietatea ca pentru oricare doua noduri adiacente (pe drum) i si j, 0 < f(i,j) ≤ cap(i,j)
  2. se alege muchia pentru care valoarea cap(i,j)-f(i,j) este minima (fie ea cmin), unde i si j sunt doua noduri adiacente (pe drum)
  3. 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)
  4. se creste valoarea fluxul total cu cmin
  5. algoritmul se repeta de la pasul 1

O descriere detaliata a algoritmului o gasiti aici.

Solutia de 100 de puncte

Abordarea lui Ford Fulkerson nu poate fi folosita pentru obtinerea punctajului maxim, din cauza complexitatii prea mari. Exista, insa, doi algoritmi care efectueaza mult mai putine operatii si care pot rezolva problema fluxlui maxim pentru limitele date:

  1. algoritmul lui Dinic, avand complexitatea O(N2*M).
  2. algoritmul lui Karzanov (mai greu de implementat), avand complexitatea O(N3)

Ambele abordari impreuna cu mai multa teorie despre flux maxim in retele au fost inglobate intr-un articol de catre Mugurel Ionut Andreica.

Probleme asemanatoare

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?