Diferente pentru problema/maxflow intre reviziile #24 si #31

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="maxflow") ==
O retea de transport este un graf orientat in care fiecare muchie are asociata o capacitate si o anumita cantitate de flux. Fluxul primit de fiecare muchie trebuie sa fie mai mic sau egal decat capacitatea acesteia. De asemenea, pentru fiecare nod, fluxul care intra in nod trebuie sa fie egal cu cantitatea de flux care iese din nod. Cu alte cuvinte, suma fluxurilor asociate muchiilor care intra intr-un nod trebuie sa fie egala cu suma fluxurilor asociate muchiilor care ies din nod, exceptie facand nodurile speciale $S$ si $D$, denumite sursa, respectiv, destinatie. Din noul sursa poate doar iesi flux, in timp ce in nodul destinatie poate doar intra flux. Valoarea fluxului unei astfel retele este egal cu suma fluxului care iese din sursa sau cu suma fluxului care intra in destinatie (cele doua fluxuri sunt egale).
O retea de transport este un graf orientat in care fiecare muchie are asociata o capacitate si o anumita cantitate de flux. Fluxul primit de fiecare muchie trebuie sa fie mai mic sau egal decat capacitatea acesteia. De asemenea, pentru fiecare nod, fluxul care intra in nod trebuie sa fie egal cu cantitatea de flux care iese din nod. Cu alte cuvinte, suma fluxurilor asociate muchiilor care intra intr-un nod trebuie sa fie egala cu suma fluxurilor asociate muchiilor care ies din nod, exceptie facand nodurile speciale $S$ si $D$, denumite sursa, respectiv, destinatie. Din nodul sursa poate doar iesi flux, in timp ce in nodul destinatie poate doar intra flux. Valoarea fluxului unei astfel retele este egal cu suma fluxului care iese din sursa sau cu suma fluxului care intra in destinatie (cele doua fluxuri sunt egale).
h2. Cerinta
* $1 ≤ M ≤ 5 000$
* Nodul $1$ este nodul sursa, iar nodul $N$ este nodul destinatie.
* Pentru fiecare muchie, capacitatea va fi un numar natural in intervalul {$[1, 110 000]$}.
* Nu exista nici o muchie $x$ $y$ astfel incat x sa fie egal cu $N$ sau $y$ sa fie egal cu $1$
* Nu exista nici o muchie $x$ $y$ astfel incat x sa fie egal cu $N$ sau $y$ sa fie egal cu $1$.
* Intre oricare doua noduri $x$ si $y$ exista maxim un arc, însă arcele x -> y şi y -> x pot exista simultan.
* In practica, retelele de flux contin adesea un numar mare de noduri vecine cu destinatia. Testele folosite la evaluarea vitezei algoritmului de flux de la aceasta problema au aceeasi proprietate.
h2. Exemplu
* 'Critice':problema/critice
* 'Senat':problema/senat
* 'Drumuri2':problema/drumuri2
* 'Traseu':problema/traseu
* "Two Shortest":http://acm.sgu.ru/problem.php?contest=0&problem=185
* 'Trafic':problema/trafic
* 'Paznici':problema/paznici
* 'Taramul Nicaieri':problema/harta
* 'Croco':problema/croco
* 'Joc4':problema/joc4
* "Optimal Marks":http://www.spoj.pl/problems/OPTM/
* "WorkersOnPlane":http://www.topcoder.com/stat?c=problem_statement&pm=9751&rd=13513
== include(page="template/taskfooter" task_id="maxflow") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3533