Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-12-15 22:12:17.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:critice2.in, critice2.outSursăAlgoritmiada 2013, Runda 1
AutorMihai CalanceaAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test0.5 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Critice2

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 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 din graful final.

Restricţii

  • 1 ≤ N,E ≤ 100 000
  • 1 ≤ M ≤ 200 000

Exemplu

critice2.incritice2.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?