Red Confiable

Submit solution
Points: 100
Time limit: 1.0s
Memory limit: 64M
Authors:
Rafaelff, FrankHG, wizard98
Problem type
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

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 n (n \leq 15) y m (m \leq 20) 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 m líneas tienen la forma: b1 b2 c (todos enteros positivos) indicando el costo c para conectar al edificio b1 y b2. Todas las conexiones son bidirecionales. Si aparece b1 b2, no aparecerá b2 b1.

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 -1.

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


  • 0
    Primervirgen  commented on Feb. 3, 2020, 1:25 a.m. ← edited

    Todo OK...


  • 1
    jmrh_1  commented on Jan. 29, 2020, 1:20 a.m.

    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!!!


    • 0
      Primervirgen  commented on Jan. 29, 2020, 1:50 p.m.

      Entonces, cual podria ser una posible solucion para AC


      • 0
        aniervs  commented on Jan. 29, 2020, 2:26 p.m.

        Lo q está mal es lo q dije del MST.


    • 0
      aniervs  commented on Jan. 29, 2020, 1:32 a.m.

      Ah...verdad. Lo q dije está mal.


  • 0
    Primervirgen  commented on Jan. 28, 2020, 7:00 p.m.

    Me podrian decir como resolver este ejercicio, creo que es un MST y alguna idea, agradeceria mucho una ayuda


    • 0
      aniervs  commented on Jan. 28, 2020, 7:21 p.m. ← edited

      .


    • 0
      aniervs  commented on Jan. 28, 2020, 7:05 p.m. ← edited

      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.


      • 0
        Primervirgen  commented on Jan. 29, 2020, 2:05 p.m. ← edited

        .


        • 0
          aniervs  commented on Jan. 29, 2020, 2:24 p.m.

          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).


          • 0
            elRubiusOMG  commented on Jan. 29, 2020, 4:23 p.m.

            Es mas complicado de lo que parece, gracias por la explicacion 10/10


            • 0
              aniervs  commented on Jan. 29, 2020, 11:11 p.m.

              El problema sólo resulta complicado si no sabes sacar los puentes.


  • 7
    eaperaza  commented on Jan. 25, 2020, 3:30 p.m.

    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.