Pagini recente » Diferente pentru utilizator/andru47 intre reviziile 7 si 6 | Diferente pentru utilizator/alex_mircescu intre reviziile 92 si 93 | Diferente pentru problema/semafoare intre reviziile 6 si 5 | Diferente pentru blog/problema-saptamanii-interclasare-solutie intre reviziile 10 si 11 | 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.
