| Fişierul intrare/ieşire: | kgraf.in, kgraf.out | Sursă | Algoritmiada 2012, Runda 2 |
| Autor | Adrian Budau, Serban Andrei Stan | Adăugată de |  Serban Andrei Stan •savim |
| Timp execuţie pe test | 0.9 sec | Limită de memorie | 54096 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Kgraf
Se da un graf orientat aciclic cu N noduri si M muchii si un numar natural K. Muchiilor le sunt atribuite costuri nenegative. Sa se determine un lant cu cel putin K muchii pentru care diferenta dintre suma celor mai mari K muchii de pe lant si suma celor mai mici K muchii de pe lant este maxima. Nu trebuie sa gasiti lantul efectiv, ci doar sa determinati aceasta valoare.
Date de intrare
Fişierul de intrare kgraf.in contine pe prima linie numerele N,M si K. Pe ficare dintre urmatoarele M linii se va gasi cate un triplet de forma a,b,c, cu proprietatea ca exista muchie de la a la b de cost c.
Date de ieşire
În fişierul de ieşire kgraf.out se va scrie un singur numar S reprezentand valoarea ceruta in enunt. In cazul in care nu exista nici un lant de lungime cel putin K, se va afisa ca raspuns -1.
Restricţii
- 1 ≤ N,K ≤ 300
- 0 ≤ M ≤ 900
- Costurile de pe muchii sunt numere nenegative mai mici sau egale cu 1.000.000
- Pentru 25% din teste N ≤ 15 si M ≤ 30
- Pentru alte 25% din teste N ≤ 100
- Pentru 70% din teste K ≤ 200
Exemplu
| kgraf.in | kgraf.out |
|---|---|
| 3 4 2 1 3 0 2 1 0 1 3 4 2 1 4 | 0 |
