Pagini recente » Diferente pentru problema/klexico intre reviziile 2 si 7 | Istoria paginii runda/poli_algoritmiada | Diferente pentru utilizator/marcelcodrea intre reviziile 95 si 17 | Diferente pentru utilizator/valen.valentin intre reviziile 40 si 44 | Diferente pentru problema/kgraf intre reviziile 6 si 5
Diferente pentru
problema/kgraf intre reviziile
#6 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$
* $1 ≤ M ≤ 900$
* Costurile de pe muchii sunt numere nenegative mai mici sau egale cu $1.000.000$
* $... ≤ ... ≤ ...$
h2. Exemplu
| 0
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="kgraf") ==
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
