Fişierul intrare/ieşire:flooow.in, flooow.outSursăLot Râmnicu Vâlcea 2015 - Baraj 3 Seniori
AutorMihai Nitu, Murtaza AlexandruAdăugată deatatomirTatomir Alex atatomir
Timp execuţie pe test0.2 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Flooow

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].

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ă.

Date de intrare

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.

Date de ieşire

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.

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

Exemplu

flooow.inflooow.out
3 2
5 1 2 -1 2 1
5 3 -2 3 -2 3
2 -1 -2
2 13
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?