== include(page="template/taskheader" task_id="datorii2") ==
Poveste si cerinta...
Intr-un grup de prieteni nu este un lucru iesit din comun, ca unii sa primeasca bani imprumut de la altii. Datoriile ce se formeaza astfel sunt rezolvate ulterior. De exemplu, daca Gigel ii plateste o bere lui Ghita, data viitoare va plati Ghita berea pentru amandoi si datoriile vor fi rezolvate. Daca dupa un timp mai indelungat imprumuturile nu se rezolva de la sine, grupul de prieteni se aduna pentru a rezolva problemele financiare. La o asemenea intalnire este de dorit, ca numarul de tranzactii efectuate sa fie minim. De exemplu, daca Gigel ii datoreaza lui Ghita 10 RON, iar Ghita lui Daniel tot 10 RON, este de ajuns ca Gigel sa dea 10 RON lui Daniel si toate datoriile vor fi rezolvate.
h2. Cerinta
Cunoscand toate imprumuturile ce au fost facute in grupul de prieteni, determinati o modalitate de rezolvare a datoriilor cu numar minim de tranzactii. Daca exista mai multe posibilitati cu numar minim de tranzactii, determinati o modalitate pentru care suma totala de bani tranzactionata sa fie minima. Daca exista mai multe posibilitati cu numar minim de tranzactii si suma totala de bani minima, afisati oricare dintre acestea.
h2. Date de intrare
Fisierul de intrare $datorii2.in$ ...
Fisierul de intrare $datorii2.in$ va contine pe prima linie doua numere naturale separate prin spatiu $N M$, reprezentand numarul de prieteni din grup, respectiv numarul de imprumuturi facute. Prietenii sunt numerotati de la $1$ la $N$. Urmatoarele $M$ linii vor contine cate trei numere naturale separate prin spatiu $A B C$ cu semnificatia: "$A$ trebuie sa plateasca $C$ RON lui $B$".
h2. Date de iesire
In fisierul de iesire $datorii2.out$ ...
Fisierul de iesire $datorii2.out$ va contine pe prima linie doua numere naturale separate prin spatiu $K S$, unde $K$ reprezinta numarul minim de tranzactii efectuate, iar $S$ suma totala minima pentru $K$ tranzactii. Pe urmatoarele $K$ linii se vor scrie cate trei numere naturale separate prin spatiu $X Y Z$ cu semnificatia: $X$ plateste $Z$ RON lui $Y$.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 20$
* $1 ≤ M, C ≤ 100$
h2. Exemplu
table(example). |_. datorii2.in |_. datorii2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|6 5
1 2 10
2 3 10
4 5 5
5 6 5
6 4 5
|1 10
1 3 10
|
h3. Explicatie
...
S-a efectuat o singura tranzactie: persoana $1$ a dat $10$ RON persoanei $3$. Suma minima tranzactionata este $10$ RON.
== include(page="template/taskfooter" task_id="datorii2") ==
