Link del problema: 1010 - ACM contest and Blackout

Dificultad: Medio

Problema: El problema se resume a dar los dos árboles de expansión mínima o los árboles con el menor peso dada una entrada de N $ 3<= N <= 100 $ nodos (escuelas) y M aristas (conexiones).

Ejemplo: Para cada M línea sea darán 3 números Ai, Bi y Ci. Donde Ai y Bi serán las escuelas conectadas y Ci su precio para que estén conectadas.

4 5
4 1 4
4 2 7
1 3 1
1 2 5
3 2 6
Aquí el grafo original:

Las respuestas serían 10 y 11 ya que los arboles menos costosos se pueden formar así:



Ahora, ¿cómo conseguir esto?
Solución (algoritmo de Kruskal): 
Para los que no conozcan el algoritmo o no sepa como trabaja acá hay una buena explicación e incluso una implementación descargable muy entendible pues el mismo algoritmo usa la estructura de datos Union-Find.
Si bien obtener el MST (Minimum Spanning Tree) es fácil con Kruskal ¿como haríamos para asegurar el segundo árbol más barato? La idea básicamente es guardar las aristas con las que formamos nuestro primer MST y buscar formar árboles exceptuando cada una de las aristas una por una, es decir, quitamos una de las aristas y formamos un nuevo árbol, después la siguiente arista que guardamos y formamos otro árbol, siempre quedándonos con la MENOR.
Con una de las dificultades que me enfrenté es que al hacer kruskal omitiendo arista por arista no me aseguraba que se formara un árbol es ahí donde debemos comprobar que se forme un árbol efectivamente. ¿Cómo? en nuestro Union - Find podemos saberlo checando que solo haya una raíz, pues si solo hay una quiere decir que solo hay una componente conexa (que todos los nodos están conectados y forman el árbol).
Al hacer esto omitir arista por arista, checar que solo haya una componente conexa y quedarnos con la menor, nos dará el siguiente MST o árbol menos costoso.

En el siguiente fragmento de código lo que hago es conseguir omitiendo arista por arista tener el siguiente árbol de expansión mínima, checar que solo haya una componente conexa en el arreglo de padres y quedarme con la mínima:



Y bueno eso fue todo por esta ocasión, ya saben si gustan sugerir algún tema pueden hacerlo abiertamente y espero les haya gustado comenten si hay dudas y escriban. 
Adrián Fernández @ferprogramming

Dado un conjunto de $N$ ($1 ≤ N ≤ 2000$) ciudades y $M$ ($0 ≤ M ≤ 50000$) carreteras cada una con un costo $P_i$ ($0 ≤ P_i ≤10^7$) de construcción distinto y un costo $C$ ($0 ≤ C ≤10^7$) por construir un aeropuerto, determinar el menor costo para conectar las $N$ ciudades. En este problema el aeropuerto cumple una función peculiar, ya que una carretera que va de una ciudad A a una ciudad B funciona como una arista bidireccional en un grafo; mientras que colocar un aeropuerto en una ciudad A forma una arista bidireccional con cualquiera otra ciudad que tenga un aeropuerto.

Del problema mismo sabemos que para que dos ciudades se consideren conectadas debe existir una o varias aristas entre ellas. También sabemos que para obtener el costo mínimo la forma final de las conexiones debe ser un árbol (para evitar ciclos y por tanto aristas innecesarias), ya que en un árbol solo ocuparíamos $N - 1$ aristas. De inmediato el problema nos suena como a un simple árbol de mínima expansión... pero, ¿qué sucede con los aeropuertos?

El problema nos indica que pueden existir desde $0$ hasta $50000$ carreteras, por lo cual nosotros podemos esperar que existan ciudades a las cuales no es posible llegar por ninguna carretera y por lo tanto tratar de considerarlos en un árbol de mínima expansión es imposible (llamaremos componente conexa a un conjunto de $n$ ciudades unidas con $n - 1$ carreteras), es ahí donde los aeropuertos tienen una de sus funciones principales. Otra función de los aeropuertos se da cuando construir una carretera entre A y B es más costoso que construir un áeropuerto en A y B.

Recapitulando: sabemos que pueden existir varias componentes conexas, sabemos que construyendo un aeropuerto en cada una de ellas garantizaría que estén conectadas, sabemos que a veces el costo de construir una carretera entre dos ciudades es mayor al de poner aeropuertos en ellas y por último sabemos que queremos obtener el menor costo para conectarlas todas.

Para resolverlo, partiremos de que cada una de las $N$ ciudades tiene un áeropuerto y por tanto están todas conectadas lo cual tendrá un costo $C_0$, posteriormente iremos uniendo (como si estuvieramos formando un árbol de mínima expansión) a cada unión quitaremos un aeropuerto, ya que no es necesario una vez que exista una carretera entre dos ciudades, porque estas estarían conectadas de todos modos, al hacer esto obtendremos un costo $C_i$ ($1 ≤ i ≤ Z$, $Z$ es el número de uniones que es posible realizar), lo que nos queda por hacer extraer el valor mínimo de todos los $C_i$ para obtener la respuesta.

Lo único que resta por considerar es que de este modo de resolver el problema puede suceder que al final nos quede una sola componente conexa y por tanto un solo aeropuerto, lo cual representa un gasto innecesario y por tanto no debe ser parte de nuestra solución.

long long int ans = N * C;
long long int roadCost = 0;
int airports = N;
for(int i = 0; i < roads.size(); i++){
 if(join(roads[i].o, roads[i].d)){
  roadCost += roads[i].c;
  airports--;
  ans = min(ans, roadCost + airports * C);
 }
}
if(airports == 1)
 ans = min(ans, roadCost);
pritnf("%lld\n", ans);