critice2

Critice2

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

Poveste şi cerinţă...

Se da un graf neorientat cu $N$ noduri si $M$ muchii. Vrem sa adaugam la acest graf alte $E$ muchii, insa vom adauga o muchie $i$ din cele $E$ muchii cu probabilitatea $P[i]$. Vrem ca la final sa stim numarul mediu de muchii din graf.

h2. Date de intrare

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

Fişierul de intrare $critice2.in$ va contine pe prima linie doua numere naturale $N$ si $M$ cu semnificatia din enunt. Pe urmatoarele $M$ linii se vor afla $M$ perechi de numere reprezentand muchiile din graful initial. Pe linia $M+2$ se va afla numarul natural $E$, cu semnificatia din enunt. Pe urmatoarele $E$ linii se vor afla $E$ triplete de numere $x y p$, reprezentand faptul ca vom adauga muchia $x-y$ cu probabilitate $p$ in graful final.

h2. Date de ieşire

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

În fişierul de ieşire $critice2.out$ trebuie sa afisati cu o precizie de **6** zecimale numarul mediu de muchii din graful final.

h2. Restricţii

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

* $1 ≤ N,E ≤ 100 000$
* $1 ≤ M ≤ 200 000$

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

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

| 3 4
1 2
2 3
2 4
3 4
1
1 4 0.3
| 3.700000 |
| 8 9
1 2
2 3
3 4
4 1
1 5
5 6
6 7
7 5
7 8
3
2 8 0.5
6 8 0.123
4 7 0.752
| 7.217496 |

h3. Explicaţie
 
...

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