Untitleds
Posted by Anonymous on Sun 4th Dec 2011 03:23
raw | new post
modification of post by Anonymous (view diff)

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define TRUE  1
#define FALSE 0
#define DEBUG 0

#define MAX_TOWNS 752

typedef struct Highway Highway;
struct Highway {
  int    from, to, done, old;
  double distance;
};

typedef struct City City;
struct City {
  int x, y, connected;
};

int     highways_done;
int     highways_count;
Highway highways[(MAX_TOWNS*MAX_TOWNS)/2];

int sets_count;
int sets_luid;
int sets[MAX_TOWNS];

int  cities_count;
int  cities_connected;
City cities[MAX_TOWNS];

double distance(int from, int to){
  return sqrt((cities[from].x-cities[to].x)*((cities[from].x-cities[to].x))+(cities[from].y-cities[to].y)*(cities[from].y-cities[to].y));
}

Highway *highway(int from, int to){
  if(from == to) return NULL;

  if(from < to){
    return &highways[from+(to-1)*to/2];
  }else{
    return highway(to, from);
  }
}

int create_cicles(Highway *hw){
  if(sets[hw->from] == -1)           return FALSE;
  if(sets[hw->to]   == -1)           return FALSE;
  if(sets[hw->from] == sets[hw->to]) return TRUE;
  return FALSE;
}

void merge_sets(int from, int to){
  int i, set_id;

  if(sets[from] == -1 && sets[from] == sets[to]){
    sets[to]   = sets_luid;
    sets[from] = sets_luid;
    sets_luid++;
    sets_count++;
    return;
  }

  if(sets[from] == -1){
    sets[from] = sets[to];
    return;
  }

  if(sets[to] == -1){
    sets[to] = sets[from];
    return;
  }

  if(sets[from] == sets[to]) return;

  set_id = sets[to];
  for(i = 0; i < cities_count; i++){
    if(set_id == sets[i]){
      sets[i] = sets[from];
    }
  }
  if(sets_count > 1) sets_count--;
}

int ended(){
  if(cities_connected == cities_count && sets_count == 1) return TRUE;
  return FALSE;
}

void build_highway(Highway *hw){
  if(!cities[hw->to].connected){
    cities[hw->to].connected = TRUE;
    cities_connected++;
  }

  if(!cities[hw->from].connected){
    cities[hw->from].connected = TRUE;
    cities_connected++;
  }

  merge_sets(hw->from, hw->to);
  hw->done = TRUE;
  highways_done++;
}

void add_highway_by_cities(int from, int to){
  highway(from, to)->old = TRUE;
  build_highway( highway(from, to) );
}

void initialize_highways(){
  int from, to;
  Highway *hw;

  highways_count = 0;
  for(to = 1; to < cities_count; to++){
    for(from = 0; from < to; from++){
      highways_count++;
      hw = highway(from, to);

      hw->to       = to;
      hw->old      = FALSE;
      hw->from     = from;
      hw->done     = FALSE;
      hw->distance = distance(from, to);
    }
  }
}

int compare_highways(const void *highway_a, const void *highway_b){
  // if(((Highway*)highway_a)->done) return 1;
  // if(((Highway*)highway_b)->done) return -1;
  if(((Highway*)highway_a)->distance > ((Highway*)highway_b)->distance) return 1;
  if(((Highway*)highway_a)->distance < ((Highway*)highway_b)->distance) return -1;
  return 0;
}

void debug_highways(){
  int i;
  printf("\n\n");
  for(i = 0; i < highways_count; i++){
    printf("Highway: (%3d, %3d) %d %d %lf\n", highways[i].from, highways[i].to, highways[i].done, highways[i].old, highways[i].distance);
  }
}

void kruskal(){
  int i;
  Highway *hw;
  qsort(highways, highways_count, sizeof(Highway), compare_highways);
  if(DEBUG) debug_highways();

  for(i = 0; i < highways_count; i++){
    if( !highways[i].done && !create_cicles(&highways[i]) ){
      if(DEBUG) printf("(%3d,%3d)-(%3d,%3d)-(%d==%d, %d)\n", highways[i].from, highways[i].to, sets[highways[i].from], sets[highways[i].to], cities_connected, cities_count, sets_count);
      build_highway(&highways[i]);
      printf("%d %d\n", highways[i].from+1, highways[i].to+1);
      if(ended()) break;
    }
  }
}

int main(){
  int i, j, from, to;
  int test_cases;

  scanf("%d", &test_cases);

  for(i = 0; i < test_cases; i++){
    scanf("%d", &cities_count);
    sets_count       = 0;
    sets_luid        = 0;
    cities_connected = 0;
    for(j = 0; j < cities_count; j++){
      scanf("%d %d", &(cities[j].x), &(cities[j].y));
      cities[j].connected = FALSE;
      sets[j] = -1;
    }

    initialize_highways();
    scanf("%d", &highways_done);
    for(j = highways_done; j > 0; j--){
      scanf("%d %d", &from, &to);
      if(from == to){
        highways_done--;
      }else{
        if(highway(from-1, to-1)->done){
          highways_done--;
        }else{
          add_highway_by_cities(from-1, to-1);
        }
      }
    }

    // printf("(%d==%d, %d)\n", cities_connected, cities_count, sets_count);

    if(ended() || cities_count == 1){
      printf("No new highways need\n");
    }else{
      if(DEBUG) debug_highways();
      kruskal();
      if(DEBUG) debug_highways();
    }

    if(i+1 < test_cases) printf("\n");
  }

  return 0;
}