Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | critice2.in, critice2.out | Sursă | Algoritmiada 2013, Runda 1 |
| Autor | Mihai Calancea | Adăugată de |  Serban Andrei Stan •savim |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Critice2
Se da un graf neorientat conex 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 critice din graf.
Date de intrare
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.
Date de ieşire
În fişierul de ieşire critice2.out trebuie sa afisati cu o precizie de 6 zecimale numarul mediu de muchii critice din graful final.
Restricţii
- 1 ≤ N,E ≤ 100 000
- 1 ≤ M ≤ 200 000
Exemplu
| critice2.in | critice2.out |
|---|---|
| 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.217496 |
