Fişierul intrare/ieşire:arb4.in, arb4.outSursăAlgoritmiada 2015, Runda 3
AutorEugenie Daniel PosdarascuAdăugată dea_h1926Heidelbacher Andrei a_h1926
Timp execuţie pe test0.7 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.inarb4.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?