== include(page="template/taskheader" task_id="flux1") ==
Se ne imaginam o retea formata din $M$ tevi. Lichidul pe o teava se scurge intr-un anumit sens, iar fiecare teava are un anumit diametru, deci prin aceasta nu poate trece mai mult lichid decat o cantitate limita (specifica fiecarei tevi). Tevile sunt conectate intre ele prin jonctiuni numerotate de la $1$ la $N$. Jonctiunea $1$ este legata la un robinet, iar jonctiunea $N$ este legata la o scurgere. In afara de acestea doua, lichidul nu se poate acumula in nico alta jonctiune (cantitatea de lichid care intra trebuie sa fie egala cu cea care iese).
Se cere sa se determine cantitatea totala maxima de apa ce poate trece de la la robinet la scurgere.
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:
Reteaua se va da sub forma unui graf orientat cu $N$ noduri (jonctiunile) si $M$ muchii (tevile), fiecare muhcie avand o anumita capacitate (debitul).
# 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)$
# ∀ $i$ ∈ $V$ avem <tex>\sum_{j \in V}^{} f(i,j) = 0</tex>
Valoarea fluxului este <tex>F = \sum_{(S,i) \in E}^{} f(S,i)</tex>, adica fluxul total care pleaca din nodul sursa.
h2. Cerinta
Se cere sa se determine valoarea maxima a fluxlui.
h2. 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$. Linia $i+1$ semnifica faptul ca teava respectiva este marginita de jonctiunile $a$ si $b$, apa se scurge de la $a$ spre $b$, iar debitul acesteia este $c$.
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$.
h2. Date de iesire
In fisierul de iesire $flux1.out$ se va scrie cantitatea totala maxima de apa ce poate trece de la la robinet la scurgere
In fisierul de iesire $flux1.out$ se va scrie fluxul maxim.
h2. Restrictii
* $1 ≤ N ≤ 200$
* $1 ≤ N ≤ 19 900$
* capacitatea fiecarei tevi este un numar natural nenul mai mic sau egal cu 150.
* fluxul maxim va fi ≤ 2 000 000 000
* $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$
h2. Exemplu
table(example). |_. flux1.in |_. flux1.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
h3. Explicatie
h2. Indicatii de rezolvare
h3. Solutia de 50 de puncte
Problema se rezolva cu ajutorul algoritmului "Ford Fulkerson":http://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm, care are urmatorii pasi.
# se cauta un drum de la sursa la destinatie (fie acesta $1 -> i{~1~} -> i{~2~} -> ... -> i{~k~} -> N$) cu proprietatea ca pentru oricare doua noduri adiacente (pe drum) $i$ si $j$, $0 < f(i,j) ≤ cap(i,j)$
# 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)
# se cresc cu $cmin$ $f(1,i{~1~}), f(i{~1~},i{~2~}), ..., f(i{~k~},N)$ si se scad cu $cmin$ $f(i{~1~},1), f(i{~2~},i{~1~}), ..., f(N,i{~k~})$
# se creste valoarea fluxul total cu $cmin$
# algoritmul se repeta de la pasul $1$
O descriere detaliata a algoritmului o gasiti "aici":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow.
h3. 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:
# algoritmul lui Dinic, avand complexitatea $O(N^2^*M)$.
# algoritmul lui Karzanov (mai greu de implementat), avand complexitatea $O(N^3^)$
Ambele abordari impreuna cu mai multa teorie despre flux maxim in retele au fost inglobate intr-un "articol":http://infoarena.ro/downloads?action=download&file=flux_maxim_in_retele.doc de catre Mugurel Ionut Andreica.
h2. Probleme asemanatoare
...
* PKU = "Ombrophobic Bovines":http://acm.pku.edu.cn/JudgeOnline/problem?id=2391
* infoarena = "Critice":http://infoarena.ro/problema/critice
* infoarena = "Tero":http://infoarena.ro/problema/tero
== include(page="template/taskfooter" task_id="flux1") ==
