Pagini recente » Diferente pentru utilizator/cpopescu1 intre reviziile 5 si 6 | Diferente pentru ia_in_ie7 intre reviziile 15 si 5 | Diferente pentru problema/joc19 intre reviziile 5 si 4 | Diferente pentru utilizator/jaddy intre reviziile 1 si 3 | Diferente pentru problema/arb2 intre reviziile 8 si 3
Diferente pentru
problema/arb2 intre reviziile
#8 si
#3
Diferente intre titluri:
Diferente intre continut:
== include(page="template/taskheader" task_id="arb2") ==
Se dă un arbore $T$ cu $n$ noduri, numerotate de la $1$ la $n$, având rădăcina în nodul $1$. Fiecare muchie $(x, y)$, de la nodul $x$ la nodul $y$, al arborelui are o lungime dată, $d{~(x, y)~}$. Rădăcina transmite un mesaj tuturor celorlalte noduri din arbore. Timpul după care o frunză primeşte mesajul este egal cu suma lungimilor muchiilor de pe drumul de la rădăcină la această frunză.
Se dă un arbore $T$ cu $n$ noduri, numerotate de la $1$ la $n$, având rădăcina în nodul $1$. Fiecare muchie $(x, y)$ de la nodul $x$ la nodul $y$ al arborelui are o lungime dată, $d{~(x, y)~}$. Rădăcina transmite un mesaj tuturor celorlalte noduri din arbore. Timpul după care o frunză primeşte mesajul este egal cu suma lungimilor muchiilor de pe drumul de la rădăcină la această frunză.
Se doreşte ca durata transmisiei mesajului de la rădăcină la fiecare frunză să fie identică. Pentru aceasta avem la dispoziţie operaţia de incrementare, care poate fi aplicată asupra oricărei muchii $(x, y)$ şi constă în creşterea lungimii muchiei cu o unitate. Costul aplicării operaţiei de incrementare asupra unei muchii $(x, y)$ este $c{~(x, y)~}$. Operaţia poate fi aplicată în mod repetat asupra aceleiaşi muchii.
h2. Date de intrare
Pe prima linie a fişierului de intrare $arb2.in$ se află numărul natural $n$. Următoarele $n - 1$ linii conţin câte patru numere naturale $x y d{~(x, y)~} c{~(x, y)~}$, separate prin câte un singur spaţiu, având semnificaţia din enunţ.
Pe prima linie a fişierului de intrare $arb.in$ se află numărul natural $n$. Următoarele $n - 1$ linii conţin câte patru numere naturale $x y d{~(x, y)~} c{~(x, y)~}$, separate prin câte un singur spaţiu, având semnificaţia din enunţ.
h2. Date de ieşire
În fişierul de ieşire $arb2.out$ se va scrie pe prima linie costul minim cerut.
În fişierul de ieşire $arb.out$ se va scrie pe prima linie costul minim cerut.
h2. Restricţii
* $1 ≤ n ≤ 100 000$
* $1 ≤ d ≤ 10 000$
* $1 ≤ c ≤ 10 000$
* Pentru $20%$ din teste $n$ va fi egal cu $3$.
* Pentru alte $30%$ din teste costul operaţiei de incrementare pentru orice muchie va fi egal cu $1$.
* Pentru $10%$ din teste $n$ va fi egal cu 3.
* Pentru $50%$ din teste costul operaţiei de incrementare pentru orice muchie va fi egal cu $1$.
h2. Exemplu
Nu exista diferente intre securitate.
Diferente intre topic forum:
