Se dă un graf conex neorientat G
cu N
noduri și M
muchii, fiecare muchie având asociat un cost. Un arbore parțial pentru G
este un subgraf cu structura de arbore, care cuprinde toate nodurile și o parte din muchii.
Cerința
Se cere găsirea unui arbore parțial al grafului G
, astfel încât diferența dintre cel mai mare și cel mai mic cost al unei muchii să fie minimă.
Date de intrare
Fișierul de intrare weightdif.in
conține pe prima linie numerele N
și M
, separate printr-un spațiu. Pe urmatoarele M
linii se vor găsi muchiile grafului sub forma X
Y
C
, cu semnificația că există muchie neorientată între X
și Y
de cost C
.
Date de ieșire
Fișierul de ieșire weightdif.out
va conține pe prima linie diferența minimă dintre cel mai mare și cel mai mic cost al muchiilor unui arbore parțial din G
.
Restricții și precizări
2 ≤ N ≤ 30.000
1 ≤ M ≤ 100.000
1 ≤ X < Y ≤ N
1 ≤ C ≤ 1.000.000.000
- între oricare două noduri există cel mult o muchie.
- Pentru 20 de puncte,
1 ≤ M ≤ 20
- Pentru 20 de puncte,
2 ≤ N ≤ 100
și1 ≤ M ≤ 100
- Pentru 20 de puncte,
2 ≤ N ≤ 1000
și1 ≤ M ≤ 10.000
- Pentru 20 de puncte,
M * (M − N) * (M − N) ≤ 10.000.000
- Pentru 20 de puncte, fără restricții adiționale
Exemplu:
weightdif.in
6 10 1 2 2 2 3 1 3 4 2 4 5 1 5 6 2 1 6 1 1 4 20 2 5 5 2 6 6 4 6 7
weightdif.out
1
Explicație
Graful din exemplu:
Un arbore parțial cu diferența minimă dintre costul maxim și cel minim de pe muchii: