| 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. 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.
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 4 zecimale numarul mediu de muchii critice din graful final.
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
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.562500 |
| 5 5 1 2 1 2 3 1 3 4 4 5 2 1 1 0.283000 1 5 0.510200 | 1.469400 |
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.
