Bacalaureat · Grafuri și arbori · clasa a 12-a
Rețeaua cea mai ieftină (APM)
Cerință
Se dă un graf neorientat conex cu costuri. Afișează costul total minim al unei submulțimi de muchii care leagă toate nodurile (arbore parțial de cost minim).
Problemă originală de antrenament, nu este subiect oficial.
Date de intrare
Pe prima linie n și m, apoi m linii x y c.
Date de ieșire
Un singur număr. Nu afișa mesaje suplimentare.
Restricții
- 1 ≤ n ≤ 50 000, 1 ≤ c ≤ 1000
- Sunt 20 de teste, fiecare valorează 5 puncte.
4 5 1 4 55 3 4 385 2 3 316 1 3 477 1 2 54
425
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Kruskal: sortează muchiile după cost și ia muchia dacă unește două componente diferite. Rezultatul corect pentru acest exemplu este: 425.
7 8 3 4 400 5 7 800 6 7 300 4 5 222 2 4 353 4 7 382 1 4 638 2 6 728
2295
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Kruskal: sortează muchiile după cost și ia muchia dacă unește două componente diferite. Rezultatul corect pentru acest exemplu este: 2295.
21 26 4 17 788 2 3 870 12 16 349 20 21 234 4 20 860 10 19 821 14 20 885 11 20 175 9 14 371 3 13 712 3 11 902 8 9 103 18 19 741 6 15 344 3 19 489 5 6 480 18 20 891 4 8 515 1 9 386 1 18 592 3 7 656 1 12 985 7 19 303 6 19 638 3 4 770 8 16 128
9899
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Kruskal: sortează muchiile după cost și ia muchia dacă unește două componente diferite. Rezultatul corect pentru acest exemplu este: 9899.