== include(page="template/taskheader" task_id="flooow") ==
Poveste şi cerinţă...
AxonT vrea să vadă dacă aveţi flooow. Se da o reţea de flux, cu costuri pe muchii, alcătuită din următoarele componente:
* Nodurile $S$ si $T$, dispuse fiecare pe câte un rand.
* Mulţimea $V$ de noduri dispusă pe $N$ rânduri, fiecare rând fiind alcătuit din $L[i]+1$ noduri $(1≤ i ≤ N)$.
* Nodul $D$ asezat pe ultimul rând.
* De la nodul $S$ la nodul $T$ este o muchie de capacitate $K$ şi cost $0$.
* De la nodul $T$ la fiecare nod de pe primul rând din multimea $V$ sunt muchii de capacitate $K$ şi cost $0$.
* De la fiecare nod de pe rândul $i$ la fiecare nod de pe rândul $i+1$ (din multimea $V$) există muchie (orientată) de capacitate $K$ şi cost $0$.
* De la fiecare nod de pe ultimul rând (rândul $N$) la nodul $D$ sunt muchii de capacitate $K$ şi cost $0$.
* De la al $j$-lea nod de pe linia $i$ către al $j+1$-lea nod de pe linia $i$, $1 ≤ i ≤ N$ si $1 ≤ j ≤ L[i]$) există o muchie de capacitate $1$ şi cost $A[i][j]$.
h2. Cerinta
Ştiind că $S$ este sursa fluxui si $D$ este destinaţia, şi dându-se numerele $N, K$, precum şi matricea $A$, să se determine fluxul maxim de cost maxim pe reteaua descrisă.
!problema/flooow?floow_image.png!
h2. Date de intrare
Fişierul de intrare $flooow.in$ ...
Pe prima linie a fişierului *flooow.in* se găsesc $2$ numere $N$ şi $K$ cu semnificaţia din enunţ/desen. Vor urma $N$ linii ce descriu matricea $A$. Fiecare dintre cele $N$ linii începe cu un număr $L$, numărul de muchii dintre nodurile de pe această linie (vor fi $L+1$ noduri). Tot pe aceasta linie vor urma $L$ numere naturale, costurile celor $L$ muchii.
h2. Date de ieşire
În fişierul de ieşire $flooow.out$ ...
Pe prima linie a fişierului *flooow.out* se vor afişa două numere naturale separate prin câte un spaţiu: cantitatea maximă de flux care poate fi transportata de la $S$ la $D$ şi costul maxim pentru a transporta această cantitate de flux.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 <= N <= 200 000$
* $1 <= numărul de noduri de pe un rând <= 200 001$
* $1 <= numarul de elemente din matricea A <= 200 000$
* $-10 000 <= orice valoare din matricea A <= 10 000$
* $1 <= K <= 5 000$
h2. Exemplu
table(example). |_. flooow.in |_. flooow.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 2
5 1 2 -1 2 1
5 3 -2 3 -2 3
2 -1 -2
| 2 13
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="flooow") ==
