Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-01-17 22:21:48.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:kgraf.in, kgraf.outSursăAlgoritmiada 2012, Runda 2
AutorAdrian Budau, Serban Andrei StanAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test1.8 secLimită de memorie54096 kbytes
Scorul tăuN/ADificultateN/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 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

  • ... ≤ ... ≤ ...

Exemplu

kgraf.inkgraf.out
3 4 2
1 3 0
2 1 0
1 3 4
2 1 4
0

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?