Fişierul intrare/ieşire:copsamica.in, copsamica.outSursăLot Râmnicu Vâlcea 2015 - Baraj 3 Seniori
AutorAdrian Budau, Vlad GavrilaAdăugată deatatomirTatomir Alex atatomir
Timp execuţie pe test1 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Copșa Mică

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 ai şi bi poate trece un debit maxim di 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 (ai, bi, di) care definesc conductele reţelei, dar a putut să afle pentru fiecare pereche de cazane (x, y) care este debitul maxim dmaxx,y de apă care poate circula de la cazanul x la cazanul y. Astfel, spunem că o reţea produce matricea dmaxx,y dacă dmaxx,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)), dmaxx,y = min(dt1, dt2, ... dtk) + min(dw1, dw1, ... dw(n-k)).

Cerinta

Dându-se N şi matricea dmaxx,y, să se reconstituie o reţea formată din N cazane şi N muchii definite prin tripletele de valori (ai, bi, di) care produce matricea dmaxx,y.

Date de intrare

Fişierul de intrare copsamica.in va conţine pe prima linie un număr natural T, semnificând numărul de reţele din fişierul de intrare. Pe liniile următoare se vor afla descrierile celor T reţele. O astfel de descriere va conţine pe prima linie numărul natural N. Urmează N-1 linii, pe linia x aflându-se câte N-x numere naturale separate prin câte un spaţiu: al y-lea număr este egal cu valoarea dmaxx,x + y.

Date de ieşire

În fişierul de ieşire copsamica.out veţi afişa cele T răspunsuri aferente celor T reţele. Răspunsul aferent unei perechi (N,dmaxx,y) este format din N linii conţinând trei numere naturale ai, bi şi di, reprezentând descrierile celor N muchii ce compun o reţea care produce matricea dmaxx,y.

Restricţii

  • T = 5
  • 3 ≤ N ≤ 1000
  • Pentru 60% din teste N ≤ 500
  • 1 ≤ dmaxx,y ≤ 20 000
  • dmaxx,y = dmaxy,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.

Exemplu

copsamica.incopsamica.outExplicatie
1
4
2 2 2
3 3
3
1 3 1
3 2 2
2 4 2
1 4 1
Pentru prima pereche (N,dmax x,y), putem construi reţeaua circulară formată din muchiile
a1 = 1, b1 = 3, d1 = 1
a2 = 3, b2 = 2, d2 = 2
a3 = 2, b3 = 4, d3 = 2
a4 = 1, b4 = 4, d4 = 1
Această reţea produce matricea dmax x,y.
Spre exemplu,
dmax1,3 = min(d1) + min(d2, d3, d4) = 1+1 = 2.
dmax2,4 = min(d2, d3) + min(d1, d4) = 2+1 = 3.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?