árbol de expansión
Problem
Se requiere para encontrar un árbol de expansión de peso mínimo en un gráfico conectado.
Entrada
La primera línea del archivo de entrada contiene dos números naturales n y m: el número de vértices y aristas del gráfico, respectivamente (1≤n≤20000, 0≤m≤100000). Las siguientes m líneas contienen la descripción de los bordes, una por línea. El número de arista i se describe mediante tres números naturales bi, ei y wi - los números de los extremos de la arista y su peso, respectivamente (1≤bi,ei≤n, 0≤wi≤100000).
El gráfico está conectado.
Salida
Imprime un solo entero: el peso del árbol de expansión mínimo.
| Entrada |
Salida |
|
4 4
1 2 1
2 3 2
3 4 5
4 1 4
|
7 |