Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-01-17 22:14:07.
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 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.

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?