g35coupe

#include "stdio.h"#include "stdlib.h"#include "unistd.h"#define MAX_VERTICES 256char *edge1,*edge2;   // Edges we store in herechar *edges;   // NxN matrix :)char vtex[MAX_VERTICES];  // vtex[i] = vertices availablechar posn[MAX_VERTICES];  // posn[i] = where is vertex i?char best[MAX_VERTICES];  // the best permutation so farchar used[MAX_VERTICES];  // tracks vertices used in the solutionchar maxl[MAX_VERTICES];  // tracks max len of edge during backtrackingchar rmap[MAX_VERTICES];  // used for dynamic randomizingchar larg[MAX_VERTICES];  // used to keep track of the first largest edgeint n; // number of verticesint m; // number of edgesint minv;  // Smallest longest edgeint cnt=0;int glug=0;inline int max_edge() {  int v=0, maxv=0, v1,v2;  for (int i=0; i<m; i++) {     v1=edge1[i];    v2=edge2[i];    v = abs(posn[v2]-posn[v1]);    if (v > maxv) {       maxv = v;      glug=v1; if (random()%2) glug=v2;    }  }  return maxv;}void find_sol(int level) {  int nv, len, a, b, j, k;  int i;   int t,w, flag, nv2;  if (level==n) {    int maxv=max_edge(); // maxl[level-1];    if (maxv<minv) {       minv=maxv;      for (int i=0; i<n; i++) best[i]=vtex[i];      printf("Min is now: %d\n", minv);    }  } else {    for (i=0; i<m; i++) {      if (used[edge1[i]] && !used[edge2[i]])         if (posn[edge1[i]] <= level-minv) return;      if (!used[edge1[i]] && used[edge2[i]])         if (posn[edge2[i]] <= level-minv) return;    }    for (int k=0; k<n; k++) {      i=rmap[k];      if (!used[i]) {        used[i]=1;        vtex[level]=i;        posn[i]=level;        find_sol(level+1);        used[i]=0;      }    } // end of main for loop  }}  void main() {  int i, j, v1, v2;  fprintf(stderr, "Starting O(1) work...\n");  scanf("%d", &n);   // Read initial data  scanf("%d", &m);    edge1 = (char *)malloc(m);  // Fix some space for edges  edge2 = (char *)malloc(m);  // Fix some space for edges  edges = (char *)malloc(256*n); // The adjacency matrix  for (i=0; i<256*n; i++) edges[i]=0;  int ecnt=0;  for (i=0; i<m; i++) {        // Start reading edges    scanf("%d %d", &v1, &v2);    v1--; v2--;    if (v1!=v2 && (v1>=0 && v1<n && v2>=0 && v2<n)) { // Loops don't matter      edge1[ecnt]=v1;      edge2[ecnt]=v2;      ecnt++;      edges[(v1<<8)+v2]=1;      edges[(v2<<8)+v1]=1;    }  }  m=ecnt;    for (i=0; i<n; i++) { // No vertices used up yet    vtex[i]=i;    used[i]=0;    posn[i]=i;    rmap[i]=i;  }  srandom(getpid()*1001);  for (i=0; i<1000; i++) {    v1 = random() % n;    v2 = random() % n;    j=rmap[v1]; rmap[v1]=rmap[v2]; rmap[v2]=j;  }  int om, nm, cnt;  for (i=0; i<1000; i++) {    v2 = random() % n;    om = max_edge();    v1=posn[glug];    cnt=0;    do {      j=vtex[v1]; vtex[v1]=vtex[v2]; vtex[v2]=j;      posn[vtex[v1]]=v1;      posn[vtex[v2]]=v2;      nm=max_edge();      if (nm>om) {	j=vtex[v1]; vtex[v1]=vtex[v2]; vtex[v2]=j;	posn[vtex[v1]]=v1;	posn[vtex[v2]]=v2;      };      cnt++;      v2 = random() % n;    } while (nm>=om && cnt<50);  }  minv = max_edge();  for (i=0; i<n; i++) best[i]=vtex[i];     for (i=0; i<n; i++) { // No vertices used up yet    vtex[i]=i;    used[i]=0;    posn[i]=i;    rmap[i]=i;  }      fprintf(stderr, "Starting O(f(n)) work...\n");  printf("Good starting minimum: %d\n", minv);  find_sol(0);  // here we go.  fprintf(stderr, "Done.\n");    fprintf(stderr, "Solution: ");  for (i=0; i<n; i++) fprintf(stderr, "%d ", best[i]+1);  fprintf(stderr, "\n");    fprintf(stderr, "Bandwidth: %d\n", minv);  }