Fişierul intrare/ieşire:mst.in, mst.outSursăLot Cluj 2009, Baraj 4
AutorMarius StroeAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test0.25 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Mst

Fie G un graf neorientat conex. Fiecare muchie e are la momentul t un cost dat de o funcţie polinomială de gradul al doilea fe(t) = ae * t2 + be * t + ce.

Cerinţă

Găsiţi timpul t la care costul arborelui de acoperire minim al lui G este cât mai mic posibil, precum şi acest cost.

Date de intrare

Pe prima linie a fişierului de intrare mst.in se găsesc două numere naturale N şi M, separate printr-un spaţiu, reprezentând numărul nodurilor din graf, respectiv numărul muchiilor. Pe linia i + 1 (1 ≤ i ≤ M) se găsesc numerele ui vi ai bi ci, separate prin câte un spaţiu, unde ui şi vi sunt capetele muchiei, iar ai, bi, ci coeficienţii funcţiei polinomiale.

Date de ieşire

Pe prima linie a fişierului de ieşire mst.out se vor scrie două numere reale cu 6 zecimale, primul fiind timpul căutat iar al doilea costul arborelui de acoperire minim în acel moment de timp.

Restricţii şi precizări

  • 2 ≤ N ≤ 100
  • 1 ≤ M ≤ 100
  • 0 ≤ ui, vi < N, oricare 1 ≤ i ≤ M
  • Coeficienţii ai, bi, ci sunt numere întregi a căror valoare absolută nu depăşeşte 106, oricare 1 ≤ i ≤ M.
  • Coeficientul ai > 0, oricare 1 ≤ i ≤ M.
  • Timpul t poate fi orice valoare de pe axa reală.
  • Funcţiile asociate muchiilor sunt distincte două câte două.
  • Rezultatele vor fi considerate corecte dacă nu au o eroare mai mare de 10-6 (a şasea zecimală poate să difere cu cel mult o unitate), dar se recomandă afişarea cu 9 zecimale.

Exemplu

mst.inmst.out
3 3
0 1 1 -2 1
1 2 1 -2 5
0 2 1 -8 16
1.000000 4.000000

Explicaţie

Funcţiile asociate muchiilor sunt:

  • f(0,1)(t) = t2 - 2t + 1,
  • f(1,2)(t) = t2 - 2t + 5,
  • f(2,0)(t) = t2 - 8t + 16.

Minimele funcţiilor f(0,1), f(1,2) se ating la momentul t = 1 iar suma lor este 4.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content