// Jens Kristian Jensen, dat2A 2002/2003
// G2, 14.--30. april 2003

#include <LEDA/basic.h>
#include <LEDA/list.h>
#include <LEDA/graph.h>
#include <LEDA/graph_gen.h>
#include <LEDA/node_partition.h>
#include <LEDA/edge_array.h>
#include <LEDA/array.h>
#include <LEDA/node_matrix.h>
#include <LEDA/string.h>

#include "bbTSP.h"
#include "randSelRange.cc"

// W has to be globally declared since cmp requires direct access to it
edge_array<double> W;

// Comparison function for LEDA's array A<E>:
// void A.sort(int (*cmp)(E,E), int l, int h) 
// (requires direct access to W)
int cmp(const edge& e1, const edge& e2) {
  if (W[e1] < W[e2])
    return -1;
  else
    if (W[e1] > W[e2])
      return 1;
  return 0;
}

void mstKruskal(graph& G, array<edge>& E, _1Tree& mst) {
  E.sort(cmp);
  node_partition P(G);

  edge e;
//   forall (e, mst.E) {
//     if (!G.is_hidden(e)) {
//       if (P.same_block(G.source(e), G.target(e))) {
// 	cerr << "mst contains a cycle" << endl;
// 	exit(0);
//       }
//       else {
// 	P.union_blocks(G.source(e), G.target(e));
//       }
//     }
//   }
  for(int i=0; i<E.size(); i++) {
    e = E[i];
    if (!G.is_hidden(e)) {
      node s = G.source(e);
      node t = G.target(e);
      if (!P.same_block(s, t)) {
	// Add the edge to the spanning tree...
	mst.E.append(e);
	mst.D[s]++;
	mst.D[t]++;
	// and update the components
	P.union_blocks(s, t);
	if (P.number_of_blocks() == 1) {
	  return;
	}
      }
    }
  }
  cerr << "The graph is not connected!" << endl;
  G.print(cerr);
  exit(0);
}

void mstKruskalFast(graph& G, array<edge>& E, _1Tree& mst) {
  node_partition P(G);

  int n = G.number_of_nodes();
  int k = randSelRange(2*n, 3*n, E, 0, E.size()-1, W);

  E.sort(cmp, 0, k);

  // Build a forest of the k+1 smallest edges
  edge e;
  for(int i=0; i<=k; i++) {
    e = E[i];
    if (!G.is_hidden(e)) {
      node s = G.source(e);
      node t = G.target(e);
      if (!P.same_block(s, t)) {
	// Add the edge to the spanning tree...
	mst.E.append(e);
	mst.D[s]++;
	mst.D[t]++;
	// and update the components
	P.union_blocks(G.source(e), G.target(e));
	if (P.number_of_blocks() == 1) {
	  return;
	}
      }
    }
  }
  
  // Make a list of the remaining inter-component edges
  list<edge> remainingEdges;
  for(int i=k+1; i< E.size(); i++) {
    e = E[i];
    if (!G.is_hidden(e)) {
      if (!P.same_block(G.source(e), G.target(e))) {
	// Add the edge to the list
	remainingEdges.append(e);
      }
    }
  }
  
  remainingEdges.sort(cmp);
  while (P.number_of_blocks() > 1 && !remainingEdges.empty()) {
    e = remainingEdges.pop();
    if (!G.is_hidden(e)) {
      node s = G.source(e);
      node t = G.target(e);
      if (!P.same_block(s, t)) {
	// Add the edge to the spanning tree...
	  mst.E.append(e);
	  mst.D[s]++;
	  mst.D[t]++;
	  // Add the edge to the spanning tree...
	  // and update the components
	  P.union_blocks(G.source(e), G.target(e));
	  if (P.number_of_blocks() == 1) {
	    return;
	  }
      }
    }
  }
  cerr << "The graph is not connected!" << endl;
  G.print(cerr);
  exit(0);
}

void completeGraph(graph& G, int n, array<edge>& E) {
  complete_ugraph(G, n);
  W.init(G);
  E.resize(G.number_of_edges());

  edge e;
  int i=0;
  forall_edges(e, G) {
    E[i++] = e; 
  }
}

void readInstance(graph& G, array<edge>& E) {
  string s;
  s.read(' ');
  while (s != "DIMENSION:") {
    s.read_line(); // Skip the rest of the line
    s.read(' ');   // and start reading the next
  }
  s.read_line();
  int i=0;
  while (s[i] == ' ') // Skip initial spaces
    i++;
  string DIMENSION = s(i, s.length());
  int V = atoi(DIMENSION);
  completeGraph(G, V, E); 

  while (s != "EDGE_WEIGHT_SECTION")
    s.read_line();
  
  node_matrix<edge> D(G);
  edge e;
  forall_edges  (e, G) {
    D(G.source(e), G.target(e)) = D(G.target(e), G.source(e)) = e;
  }
  
  node u, v;
  forall_nodes (u, G) {
    forall_nodes (v, G) {
      cin >> s;
      if (s.length() == 0)
	cin >> s;
      //	cout << atoi(s);
      if (u == v) { // Skip the diagonal 0 and break out of the loop
	//	  cout << endl;
	break;
      }
      else { // Assign the proper edge weight
	W[D(u,v)] = atoi(s);
      }
      //	cout << " ";
    }
  }
}

int main() {

  graph G;
  array<edge> E;
  readInstance(G, E);

  _1Tree T(G);

  return 0;
}