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. 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.inkgraf.out
3 4 2
1 3 0
2 1 0
1 3 4
2 1 4
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content