2533 - Connecting Cities (Kruskal)

Escrito por Rodrigo Burgos Domínguez

2533 - Connecting Cities (Kruskal)

Este problema se presento en un concurso de preparación para el regional 2013, el problema nos decía que hay costos de conectar una ciudad a otra, y te dan todas las posible aristas y sus costos que puedes utilizar, tu tarea es encontrar el mínimo costo de conectar todas las ciudades, esto parecería directamente un Kruskal, pero ademas de eso puede colocar aeropuertos y el costo de colocar un aeropuerto en cualquiera de la ciudades es C.

Para el caso simple nosotros podemos utilizar kruskal, suponiendo que no colocamos ningún aeropuerto, pero que pasa cuando es necesario colocar lo, lo que debemos observar que colocar una unión de una ciudad a otra por medio de un aeropuerto nos cuesta 2C, ya que no existen entre ellas un aeropuerto , pero cuando colocamos la unión de otra, por ejemplo tenemos un aeropuerto del en el nodo A y B, y ahora queremos conecta Q con P, realmente no importa la conexión de Q con P, haciendo un aeropuerto en P, podemos conectar tanto A y B con P , con el único costo C, con esta hipótesis, lo que hacemos es agregar todas las aristas de todos los nodos contra todos los nodos con costo C, y aplicar kruskal, el resultado le sumamos el costo de la primera arista que generó dos aeropuertos C.

de ahi tenemos el siguiente codigo:

/*
  Rodrigo Burgos Dominguez
*/

# include "stdio.h"
# include "string.h"

# define MAX_ARISTAS 5000000
# define MAX_NODES 2000

typedef struct { int a, b, cost; } ARISTA;

ARISTA A[MAX_ARISTAS + 1];


int set[MAX_NODES + 1];

int min( int a, int b){ return a < b ? a: b; }

int getSet( int nodo ){ 
  return set[ nodo ] == nodo ? nodo : (set[nodo] = getSet( set[nodo] ) );
}

int compare(ARISTA *a, ARISTA *b){ return a->cost - b->cost; }

int kruskal(int N, int M){
  int x, sol = 0, a, b, contAristaAgregadas  = 0;
  for( x = 0 ; x <= N; x++) set[x] = x;
  qsort( A, M, sizeof( ARISTA ), compare );
  for( x = 0; x < M; x++){
     a = getSet( A[x].a);
     b = getSet( A[x].b);
     if( a != b){
       contAristaAgregadas ++;
       set[a] = b;
       sol += A[x].cost; 
     }
  }
  return ( contAristaAgregadas  == N - 1 ) ? sol : (1<<28);
}

main(){
  int sol, ncases, cases, x, y;
  int N, M, C; 
  for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
     scanf("%d %d %d", &N, &M, &C); 
     for( x = 0; x < M; x++){
      scanf("%d %d %d", &A[x].a, &A[x].b, &A[x].cost);
     }
     sol = kruskal(N, M);
     for( x = 1; x <= N; x++)
     for( y = x + 1; y <= N ; y++) {
        A[ M ].a = x;
        A[ M ].b = y; 
        A[ M ].cost = C;
        M++;
     }
     sol =  min( sol, kruskal(N, M) + C);
     printf("%d\n", sol);
  }