Diferente pentru problema/copsamica intre reviziile #5 si #10

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="copsamica") ==
După experienţele nefericite avute anul trecut în Las Vegas, Charles a decis să nu mai joace vreodată Blackjack şi să-şi spele păcatele lucrând la curăţarea \ oraşului _Copşa Mică_, până de curând cel mai poluat oraş din Europa. El va începe prin a curăţa instalaţiile de producere a negrului de fum (sursa principală a poluării din oraş).
După experienţele nefericite avute anul trecut în Las Vegas, Charles a decis să nu mai joace vreodată Blackjack şi să-şi spele păcatele lucrând la curăţarea oraşului _Copşa Mică_, până de curând cel mai poluat oraş din Europa. El va începe prin a curăţa instalaţiile de producere a negrului de fum (sursa principală a poluării din oraş).
O astfel de reţea este formată din $N$ cazane unite între ele prin $N$ conducte, astfel încât fiecare cazan este unit prin conducte de exact două alte cazane, şi se poate ajunge de la un cazan la oricare altul urmând conductele (există exact două moduri de a ajunge de la un cazan la oricare altul). Cu alte cuvinte, reţeaua are forma unui ciclu simplu. Prin fiecare conductă $i$, ($1 ≤ i ≤ N$) care uneşte cazanele $a{~i~}$ şi $b{~i~}$ poate trece un debit maxim $d{~i~}$ de apă. Un drum de la un cazan $x$ la un alt cazan $y$ este format dintr-o serie conducte adiacente pentru care prima conductă din serie are un capăt în $x$, iar ultima conductă din serie are un capăt în $y$.
O astfel de reţea este formată din $N$ cazane unite între ele prin $N$ conducte, astfel încât fiecare cazan este unit prin conducte de exact două alte cazane, şi se poate ajunge de la un cazan la oricare altul urmând conductele (există exact două moduri de a ajunge de la un cazan la oricare altul). Cu alte cuvinte, reţeaua are forma unui ciclu simplu. Prin fiecare conductă $i$, ( $1 ≤ i ≤ N$) care uneşte cazanele $a{~i~}$ şi $b{~i~}$ poate trece un debit maxim $d{~i~}$ de apă. Un drum de la un cazan $x$ la un alt cazan $y$ este format dintr-o serie conducte adiacente pentru care prima conductă din serie are un capăt în $x$, iar ultima conductă din serie are un capăt în $y$.
Din păcate, Charles nu cunoaşte tripletele de valori $(a{~i~}, b{~i~}, d{~i~})$ care definesc conductele reţelei, dar a putut să afle pentru fiecare pereche de cazane $(x, y)$ care este debitul maxim $dmax{~x,y~} de apă care poate circula de la cazanul $x$ la cazanul $y$. Astfel, spunem că o reţea produce matricea $dmax{~x,y~}$ dacă $dmax{~x,y~}$ este egal cu:
Din păcate, Charles nu cunoaşte tripletele de valori $(a{~i~}, b{~i~}, d{~i~})$ care definesc conductele reţelei, dar a putut să afle pentru fiecare pereche de cazane $(x, y)$ care este debitul maxim $dmax{~x,y~}$ de apă care poate circula de la cazanul $x$ la cazanul $y$. Astfel, spunem că o reţea produce matricea $dmax{~x,y~}$ dacă $dmax{~x,y~}$ este egal cu:
* $0$, dacă $x = y$.
* suma debitelor minime aflate pe fiecare din cele două drumuri care unesc cazanele $x$ şi $y$. Mai exact, dacă un drum de la $x$ la $y$ trece prin conductele $(t1, t2, ... tk)$ iar celalalt trece prin conductele $(w1, w2, ... w(n-k))$, dmax{~x,y~} = $min(d{~t1~}, d{~t2~}, ... d{~tk~}) + min(d{~w1~}, d{~w1~}, ... d{~w(n-k)~})$.
* $3 ≤ N ≤ 1000$
* Pentru $60%$ din teste $N ≤ 500$
* $1 ≤ dmax{~x,y~} ≤ 20 000$
* $dmax{~x,y~} = $dmax{~y,x~}$
* $dmax{~x,y~} = dmax{~y,x~}$
* Valorile debitelor di afişate trebuie să fie numere naturale ≤ $20 000$.
* Cazanele sunt numerotate de la $1$.
* Exista cel puţin o soluţie. În cazul în care există mai multe, puteţi afişa oricare dintre ele.
2 4 2
1 4 1
| Pentru prima pereche (N,dmax ~x,y~), putem construi reţeaua circulară formată din muchiile
a ~1~ = 1, b ~1~ = 3, d ~1~ = 1
a ~2~ = 3, b ~2~ = 2, d ~2~ = 2
a ~3~ = 2, b ~3~ = 4, d ~3~ = 2
a ~4~ = 1, b ~4~ = 4, d ~4~ = 1
a{~1~} = 1, b{~1~} = 3, d{~1~} = 1
a{~2~} = 3, b{~2~} = 2, d{~2~} = 2
a{~3~} = 2, b{~3~} = 4, d{~3~} = 2
a{~4~} = 1, b{~4~} = 4, d{~4~} = 1
Această reţea produce matricea dmax ~x,y~.
Spre exemplu,
dmax ~1,3~ = min(d1) + min(d2, d3, d4) = 1+1 = 2.
dmax ~2,4~ = min(d2, d3) + min(d1, d4) = 2+1 = 3.
dmax{~1,3~} = min(d1) + min(d2, d3, d4) = 1+1 = 2.
dmax{~2,4~} = min(d2, d3) + min(d1, d4) = 2+1 = 3.
|

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.