flux1

Flux maxim

== include(page="template/taskheader" task_id="flux1") ==

Fie un graf orientat cu $N$ noduri si $M$ muchii. 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 $G$ ca fiind o functie _f: VxV -> Z_, unde $V$ este multimea nodurilor grafului. Functia _f_ satisface urmatoarele conditii:

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:

# 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 &forall; $i$ &isin; $V$ valoarea fluxului care intra in nodul respectiv este egala cu valoarea fluxlui care iese din nodul respectiv (<tex>\sum_{(i,j) \in V}^{} f(i,j) = 0</tex>)
 
Valoarea fluxului este <tex>\sum_{(i,j) \in V}^{} f(i,j)</tex>, adica suma fluxlul total care pleaca din sursa.

# 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)$
# &forall; $i$ &isin; $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 valorile functiei _f_ pentru orice muchie (i,j) astfel incat $F$ sa fie maxim.

Se cere sa se determine valoarea maxima a fluxlui.

h2. Date de intrare

h2. Restrictii

* $1 ≤ N ≤ 50$
* $1 ≤ N ≤ 1225$
* capacitatea fiecarei tevi este un numar natural nenul mai mic sau egal cu 150.
* daca in fisier exista muchia ({$a$}, {$b$}), cu siguranta nu va exista si muchia ({$b$},{$a$})
* 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 |
| 6 12

1 2 6
1 3 3
3 4 5
4 5 4
5 6 4
3 6 100
2 4 3

4 3
1 3 5

1 5 4

1 3 6
4 6 5
2 3 5
3 6 4
| 13

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

|
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 (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$

# 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^)$

*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.

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

infoarena - "Trafic":http://infoarena.ro/problema/trafic

* 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") ==