Pagini recente » Diferente pentru home intre reviziile 167 si 902 | Borderou de evaluare (job #353467) | Borderou de evaluare (job #1761281) | Cod sursa (job #1915342) | Diferente pentru problema/flux1 intre reviziile 50 si 58
Nu exista diferente intre titluri.
Diferente intre continut:
== include(page="template/taskheader" task_id="flux1") ==
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:
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 ∀ $i$ ∈ $V\{1,N}$ valoarea fluxului care intra in nodul respectiv este egala cu valoarea fluxlui care iese din nodul respectiv (∀ $i$ ∈ $V$ avem <tex>\sum_{j \in V}^{} f(i,j) = 0</tex>
Valoarea fluxului este <tex>F = \sum_{(1,i) \in E}^{} f(1,i)</tex>, adica fluxul total care pleaca din nodul sursa.
# ∀ $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
* $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, in fisierul de intrare, exista muchia $(a,b)$ poate sa existe si muchia $(b,a)$
* 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
# 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 teoria completa 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.
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
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.