Fişierul intrare/ieşire: | flooow.in, flooow.out | Sursă | Lot Râmnicu Vâlcea 2015 - Baraj 3 Seniori |
Autor | Mihai Nitu, Murtaza Alexandru | Adăugată de | |
Timp execuţie pe test | 0.1 sec | Limită de memorie | 131072 kbytes |
Scorul tău | N/A | Dificultate | N/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.in | flooow.out |
---|---|
3 2 5 1 2 -1 2 1 5 3 -2 3 -2 3 2 -1 -2 | 2 13 |