flooow

Flooow

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