#include #include #include #include using namespace std; #define DEBUG 0 const int MAX_DSIZE = 8, MAX_POINTS = 2 * MAX_DSIZE, MAX_DIST = 50; const double INF = 1e100; double best[1<<(MAX_POINTS-1)][MAX_POINTS]; int districts[MAX_DIST][MAX_DSIZE][2], dSizes[MAX_DIST], nDist; double heldKarp(double distance[MAX_POINTS][MAX_POINTS],int nPoints) { for (int i=0;i<(1<<(nPoints-1));i++) for (int j=0;j=0&&dists[i][rOrder[i][k]] > dists[i][rOrder[i][tmp]];k--) rOrder[i][k+1] = rOrder[i][k]; rOrder[i][k+1] = tmp; } } for (i=0;i=0&&dists[cOrder[i][k]][i] > dists[cOrder[i][tmp]][i];k--) cOrder[i][k+1] = cOrder[i][k]; cOrder[i][k+1] = tmp; } } /* for (i=0;i 0) { qH = ++qH % (MAX_DIST/2); qC--; tmp = q[qH]; rChoice[tmp]++; if (cChoice[rOrder[tmp][rChoice[tmp]]] == -1) { cChoice[rOrder[tmp][rChoice[tmp]]] = tmp; } else { for (i=0;cOrder[rOrder[tmp][rChoice[tmp]]][i] != tmp;i++); for (j=0;cOrder[rOrder[tmp][rChoice[tmp]]][j] != cChoice[rOrder[tmp][rChoice[tmp]]];j++); if (i < j) { q[qT] = cChoice[rOrder[tmp][rChoice[tmp]]]; cChoice[rOrder[tmp][rChoice[tmp]]] = tmp; } else { q[qT] = tmp; } qT = ++qT % (MAX_DIST/2); qC++; } } for (i=0;i> nDist; for (int i=0;i> dSizes[i]; for (int j=0;j> districts[i][j][0] >> districts[i][j][1]; generateDistances(dists,districts[i],dSizes[i]); total += heldKarp(dists,dSizes[i]); } for (int i=0;i