Revizia anterioară Revizia următoare
| 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. Muchiile au costuri nenegative. Sa se determine un lant de lungime cel putin K pentru care diferenta dintre suma celor mai mari K elemente de pe lant si suma celor mai mici K elemente 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
- ... ≤ ... ≤ ...
Exemplu
| kgraf.in | kgraf.out |
|---|---|
| 3 4 2 1 3 0 2 1 0 1 3 4 2 1 4 | 0 |
Explicaţie
...
