Fişierul intrare/ieşire:critice2.in, critice2.outSursăAlgoritmiada 2013, Runda 1
AutorMihai CalanceaAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test1 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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.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.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?