Red Confiable
Los azucareros del centro están a cargo de diseñar una red universitaria entre los edificios y están muy angustiados acerca de su fiabilidad y su costo. De esta manera, ellos han decidido construir su red mientras están cuidando que salga tan barato como sea posible. Específicamente, ellos quieren construir la red más barata para que si cualquiera línea se rompe, todos los edificios todavía puedan comunicarse. Nosotros lo llamaremos la mínima red confiable.
Entrada
La entrada comienza con un par de enteros y en una línea indicando el número de edificios (numerados de 1 hasta n) y el número de posibles conexiones inter-edificios, respectivamente. Las siguientes líneas tienen la forma: (todos enteros positivos) indicando el costo para conectar al edificio y . Todas las conexiones son bidirecionales. Si aparece , no aparecerá .
Salida
La salida debe contener en una línea el costo de la mínima red confiable. Si este mínimo no existe imprima el valor .
Ejemplo #1 de Entrada
4 5
1 2 1
1 3 2
2 4 2
3 4 1
2 3 1
Ejemplo #1 de Salida
6
Ejemplo #2 de Entrada
2 1
1 2 5
Ejemplo #2 de Salida
-1
Comments
Todo OK...
Anier creo que tu segunda idea no da AC . Si te fijas puede que adiciones una arista que no esté en el MST y aún así el grafo contenga puentes. Hazme saber si me equivoco!!!
Entonces, cual podria ser una posible solucion para AC
Lo q está mal es lo q dije del MST.
Ah...verdad. Lo q dije está mal.
Me podrian decir como resolver este ejercicio, creo que es un MST y alguna idea, agradeceria mucho una ayuda
.
Man, hay 20 aristas a lo sumo, una fuerza bruta que pruebe todos los subconjuntos de aristas es suficiente para aceptar todos los casos de prueba.
.
Bitmask sobre las aristas y chequeas que con las aristas de la actual bitmask haya una sola componente conexa y no hayan puentes (un puente es una arista que al eliminarla el grafo se desconecta).
Es mas complicado de lo que parece, gracias por la explicacion 10/10
El problema sólo resulta complicado si no sabes sacar los puentes.
El primer caso de prueba ejemplo esta incorrecto. Dan n y m, y luego deberian haber m lineas y solo hay 4. La quinta linea deberia ser 2 3 1.