h2. Restrictii

* $1 ≤ N ≤ 200$

* $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)$

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

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 descrisa 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 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.
 
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") ==