Kgraf

kgraf

== include(page="template/taskheader" task_id="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.

Poveste şi cerinţă...

h2. 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$.

Fişierul de intrare $kgraf.in$ ...

h2. 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$.

În fişierul de ieşire $kgraf.out$ ...

h2. 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$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. kgraf.in |_. kgraf.out |

| 3 4 2
1 3 0
2 1 0
1 3 4
2 1 4
| 0

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="kgraf") ==

6934