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:

h2. Date de intrare

* 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

Fişierul de intrare $flooow.in$ ...

Ş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ă.
 
h2. Date de intrare

h2. Date de ieşire