Pagini recente » Diferente pentru problema/parcele1 intre reviziile 44 si 1 | Diferente pentru utilizator/andrei.xwe intre reviziile 10 si 7 | Diferente pentru problema/reteta2 intre reviziile 9 si 10 | Diferente pentru utilizator/federer intre reviziile 6 si 1 | Diferente pentru problema/kgraf intre reviziile 15 si 5
Nu exista diferente intre titluri.
Diferente intre continut:
== 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 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.
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") ==
Nu exista diferente intre securitate.
Diferente intre topic forum:
