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.

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.

h2. Date de intrare

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

| 0
|

h3. Explicaţie
 
...
 

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

6934