Pagini recente » Monitorul de evaluare | Diferente pentru utilizator/dariusdarius intre reviziile 3 si 4 | Monitorul de evaluare | Istoria paginii utilizator/unibuc_ccc | Diferente pentru problema/kgraf intre reviziile 5 si 6
Diferente pentru
problema/kgraf intre reviziile
#5 si
#6
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$. 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.
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.
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.
