Pagini recente » Diferente pentru problema/traseu3 intre reviziile 24 si 8 | Comitat | Diferente pentru problema/tequila intre reviziile 71 si 144 | Diferente pentru problema/map intre reviziile 5 si 4 | Diferente pentru problema/dcmcp intre reviziile 8 si 4
Diferente pentru
problema/dcmcp intre reviziile
#8 si
#4
Nu exista diferente intre titluri.
Diferente intre continut:
== include(page="template/taskheader" task_id="dcmcp") ==
Sa consideram un graf neorientat avand $N$ noduri, numerotate de la $1$ la $N$, si $M$ muchii. Nodul $1$ corespunde unei mine de unde sunt extrase niste minerale pretioase. Nodul $N$ corespunde unei fabrici de prelucrare a mineralelor. Fiecare muchie are asociate o durata de traversare (exprimata in unitati de timp) si o capacitate (exprimata in unitati de minerale). S-a decis ca mineralele extrase din mina sa fie transportate la fabrica folosind un singur drum. Acest drum trebuie sa aiba cea mai mare capacitate posibila, pentru a putea transporta simultan cat mai multe unitati de minerale. Capacitatea unui drum este egala cu capacitatea minima a unei muchii de pe drum. Deoarece mineralele sunt foarte sensibile, ele se vor descompune dupa $T$ unitati de timp de la extragerea acestora din mina. Prin urmare, durata totala de traversare a drumului ales (suma duratelor de traversare ale muchiilor de pe drum) trebuie sa fie mai mica sau egala cu {$T$}.
Sa consideram un graf neorientat avand $N$ noduri, numerotate de la $1$ la $N$, si $M$ muchii. Nodul $1$ corespunde unei mine de unde sunt extrase niste minerale pretioase. Nodul $N$ corespunde unei fabrici de prelucrare a mineralelor. Fiecare muchie are asociate o durata de traversare (exprimata in unitati de timp) si o capacitate (exprimata in unitati de minerale). S-a decis ca mineralele extrase din mina sa fie transportate la fabrica folosind un singur drum. Acest drum trebuie sa aiba cea mai mare capacitate posibila, pentru a putea transporta simultan cat mai multe unitati de minerale. Capacitatea unui drum este egala cu capacitatea minima a unei muchii de pe drum. Deoarece mineralele sunt foarte sensibile, ele se vor descompune dupa T unitati de timp de la extragerea acestora din mina. Prin urmare, durata totala de traversare a drumului ales (suma duratelor de traversare ale muchiilor de pe drum) trebuie sa fie mai mica sau egala cu T.
h2. Date de intrare
h2. Restrictii
* $1 ≤ X ≤ 10$
* $1 ≤ X ≤ 20$
* $2 ≤ N ≤ 10 000$
* $1 ≤ M ≤ 50 000$
* $1 ≤ T ≤ 500 000$
== include(page="template/taskfooter" task_id="dcmcp") ==
Nu exista diferente intre securitate.
Diferente intre topic forum:
