Fişierul intrare/ieşire:	mst.in, mst.out	Sursă	Lot Cluj 2009, Baraj 4
Autor	Marius Stroe	Adăugată de	Marius Stroe •Marius
Timp execuţie pe test	0.125 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/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 f_e(t) = a_e * t² + b_e * t + c_e.

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 u_i v_i a_i b_i c_i, separate prin câte un spaţiu, unde u_i şi v_i sunt capetele muchiei, iar a_i, b_i, c_i 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 exact 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 ≤ u_i, v_i < N, oricare 1 ≤ i ≤ M
• Coeficienţii a_i, b_i, c_i sunt numere întregi a căror valoare absolută nu depăşeşte 10⁶, oricare 1 ≤ i ≤ M.
• Coeficientul a_i > 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).

Exemplu

Explicaţie

Funcţiile asociate muchiilor sunt:

• f_(0,1)(t) = t² - 2t + 1,
• f_(1,2)(t) = t² - 2t + 5,
• f_(2,0)(t) = t² - 8t + 16.

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

Cum se trimit solutii?