== include(page="template/taskheader" task_id="critice2") ==
Poveste şi cerinţă...
Se da un graf neorientat conex cu $N$ noduri si $M$ muchii. Exista si $E$ muchii fictive, o muchie $i$ din cele $E$ avand probabilitatea $P[i]$ sa apara in graf. Vrem sa stim numarul mediu de muchii critice 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 **4** zecimale numarul mediu de muchii critice din graful final.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100 000$
* $1 ≤ M,E ≤ 200 000$
* Se pot repeta muchii si pot exista muchii de la un nod la el insusi
* O muchie se considera critica daca eliminarea ei din graf ar face ca graful sa nu mai fie conex
* Raspunsul se considera corect daca diferenta dintre ce afisati si rezultatul comisiei difera prin cel mult *0.0001*
h2. Exemplu
table(example). |_. critice2.in |_. critice2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 4 4
1 2
2 3
2 4
3 4
1
1 4 0.3
| 0.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
| 0.562500 |
| 5 5
1 2
1 2
3 1
3 4
4 5
2
1 1 0.283000
1 5 0.510200
| 1.469400 |
h3. Explicaţie
h2. Explicatii
...
Pentru primul exemplu cu probabilitate $0.7$ nu apare niciuna din cele $E$ muchii. Graful astfel obtinut are o singura muchie critica. Cu probabilitate $0.3$ apare acea muchie in graf si astfel graful nu mai are nicio muchie critica. Raspunsul este deci $0.7 * 1 + 0.3 * 0 = 0.7$.
== include(page="template/taskfooter" task_id="critice2") ==
== include(page="template/taskfooter" task_id="critice2") ==
