Nuevas carreteras
El alcalde de tu ciudad ha creado barrios residenciales nuevos. El quiere conectar los barrios nuevos con carreteras de tal manera que el pueda viajar de cualquier barrio a cualquiera otro a través de carreteras; hay carreteras que ya conectan algunos de los barrios.
Cada uno de los barrios (convenientemente numerados ) está representado por una posición en el plano . Dadas las carreteras pre existentes como pares de barrios conectados, ayude al alcalde a determinar la menor longitud de carreteras adicionales que él debe construir para conectar todos los barrios.
Formato de entrada:
Línea : Dos enteros separados por espacio: y .
Líneas : Dos enteros separados por espacio: y
Líneas : Dos enteros separdos por espacio: y indicando que ya hay una carretera que conecta los barrios y .
Formato de salida:
La menor longitud de senderos adicionales requeridos para conectar todos los barrios impresa sin redondear con dos decimales. Este seguro de calcular la distancia usando números flotantes de bits.
Ejemplo de entrada
4 1
1 1
3 1
2 3
4 3
1 4
Ejemplo de salida:
4.00
Explicacion de la entrada:
Los barrios y ya están conectados por un sendero. Conectar los barrios y con un sendero que tiene unidades de longitud, luego conectar los barrios y con un sendero que tiene unidades de longitud. Esto es lo mejor que podemos hacer, y da un total de unidades de longitud.
Comments