mst

Mst

== include(page="template/taskheader" task_id="mst") ==

Poveste şi cerinţă...

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^2^ + b{~e~} * t + c{~e~}$.
 
h2. 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.

h2. Date de intrare

Fişierul de intrare $mst.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $mst.out$ ...

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.

h2. Restricţii

h2. Restricţii şi precizări

* $... ≤ ... ≤ ...$

* $2 ≤ N ≤ 100$
* $1 ≤ M ≤ 100$
* $0 &le; u{~i~}, v{~i~} < N$, oricare $1 &le; i &le; M$
* Coeficienţii $a{~i~}$, $b{~i~}$, $c{~i~}$ sunt numere întregi a căror valoare absolută nu depăşeşte $10^6^$, oricare $1 &le; i &le; M$.
* Coeficientul $a{~i~} > 0$, oricare $1 &le; i &le; 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.

h2. Exemplu
table(example). |_. mst.in |_. mst.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3 3
0 1 1 -2 1
1 2 1 -2 5
0 2 1 -8 16
|1.000000 4.000000

|
h3. Explicaţie

...

Funcţiile asociate muchiilor sunt:
 
* $f{~(0,1)~}(t) = t^2^ - 2t + 1$,
* $f{~(1,2)~}(t) = t^2^ - 2t + 5$,
* $f{~(2,0)~}(t) = t^2^ - 8t + 16$.
 
Minimele funcţiilor f{~(0,1)~}, f{~(1,2)~} se ating la momentul $t = 1$ iar suma lor este $4$.

== include(page="template/taskfooter" task_id="mst") ==

4007