Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | arb4.in, arb4.out | Sursă | Algoritmiada 2015, Runda 3 |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Heidelbacher Andrei •a_h1926 |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Arb4
Se da un graf cu N noduri si M muchii. Primele N - 1 muchii formeaza un arbore partial de cost minim. Pentru fiecare muchie i din arbore trebuie sa se spuna in cazul in care muchia i este stearsa, cu ce muchie trebuie inlocuita astfel incat costul arborelui partial sa fie minim.
Date de intrare
Fişierul de intrare arb4.in va contine pe prima linie 2 numere naturale N si M. Pe urmatoarele M linii se vor afla 3 numere naturale a b c reprezentand ca avem o muchie de la a la b de cost c. Primele N - 1 muchii din cele M formeaza arborele initial.
Date de ieşire
Fişierul de ieşire arb4.out va contine N - 1 linii. Pe linia i se va afla indicele muchiei care ar fi folosita daca am elimina muchia i din arbore. Daca muchia i nu poate sa fie inlocuita afisati -1.
Restricţii
- 1 ≤ N ≤ 100.000
- 1 ≤ M ≤ 250.000
- muchiile au costuri distincte doua cate doua din intervalul [1,1.000.000.000]
- primele N - 1 muchii formeaza un arbore partial de cost minim in graful dat
- nodurile si muchiile sunt numerotate de la 0
- intre oricare doua noduri exista cel mult o muchie si nu exista muchie de la un nod la el insusi
Exemplu
| arb4.in | arb4.out |
|---|---|
| 5 10 3 2 1 4 2 2 0 3 3 1 4 4 0 4 456867131 1 3 33364433 0 1 49309036 3 4 975587959 0 2 139619699 2 1 767959053 | 5 5 6 5 |
