ACM 题目求最优解 我TLE了求助啊.
描述：
在二维坐标上给你M个点(M是偶数)的坐标,坐标都是整数,你可以任意联接其中两点(不管中间有没有障碍),这两点就消失了(和游戏里的一样).但消去两点的路径和两个点的位置有关,也就是说路径的长度等于两点X轴与Y轴差的绝对值之和.比如一个点坐标为(10,10),另外一个点坐标为(2,3),那么消去这两个点的路径长度为8+7=15.问消去所有点的路径长度之和最小值是多少?
第一行输一个正整数N,下面有N种连连看的地图
每种地图的第一行输入一个正整数M
(M是偶数,并且2=< M <=20),代表地图上有M个点.
下面有M行,每一行都有两个整数,代表这个点的X轴坐标与Y轴坐标.
(坐标的绝对值不会大于十万)
输出共N行,每行都是消去所有点的路径长度之和的最小值.
Sample Input
3
2
10 10
2 3
2
0 1
0 2
4
0 2
0 3
0 5
0 6
Sample Output
15
1
2
-------------------------
我的方法 ：
- C/C++ code
#include <stdio.h> struct Point { int x, y; }PointList[21]; int g_nSatusList[1024][1024]; int g_nPointList[21][21]; int g_nFlagList[21] = {0}; int n = 0; int valuex = 1023, valuey = 1023;int max1 = 0, max2 = 0; int abs(int argA, int argB) { return argA > argB ? argA - argB : argB - argA; }int DeepInto(int Limit) { int i = 0 ,j = 0; if (Limit == 2) { int x = -1, y = -1; for (i = 0; i < n; i++) { if (g_nFlagList[i] == 0) { if (x == -1) x = i; else y = i; } } return g_nPointList[x][y] == 0 ? g_nPointList[y][x] : g_nPointList[x][y]; } int minitemp = 200000000; int tpj = -1; for (i = 0; i < n; i++) { if (g_nFlagList[i] == 0) { if (tpj == -1) tpj = i; //记录开始点 g_nFlagList[i] = 1; if (i < 10) valuex = (valuex ^ (1 << i)); else valuey = (valuey ^ (1 << (i - 10))); int j = 0; for (j = tpj; j < n; j++) { if (g_nFlagList[j] == 0 && minitemp > g_nPointList[i][j]) { g_nFlagList[j] = 1; if (j < 10) valuex = (valuex ^ (1 << j)); else valuey = (valuey ^ (1 << (j - 10))); int temp; if (g_nSatusList[valuex][valuey] != -1) { temp = g_nSatusList[valuex][valuey]; } else { temp = DeepInto(Limit - 2); } int ijLength = g_nPointList[i][j] == 0 ? g_nPointList[j][i] : g_nPointList[i][j]; if (minitemp > ijLength + temp) { minitemp = ijLength + temp; } if (g_nSatusList[valuex][valuey] == -1 || g_nSatusList[valuex][valuey] > minitemp) g_nSatusList[valuex][valuey] = minitemp; g_nFlagList[j] = 0; if (j < 10) valuex = (valuex ^ (1 << j)); else valuey = (valuey ^ (1 << (j - 10))); } } g_nFlagList[i] = 0; if (i < 10) valuex = (valuex ^ (1 << i)); else valuey = (valuey ^ (1 << (i - 10))); } } return minitemp; } void initailArray(int MX, int MY) { int i = 0, j = 0; for (;i < MX; i++) for(j = 0; j < MY; j++) g_nSatusList[i][j] = -1; } int main () { int CaseN = 0; while (1 == scanf("%d", &CaseN)) { while (CaseN--) { scanf("%d", &n); int i = n; max1 = 0, max2 = 0; while (i--) { scanf("%d %d", &PointList[i].x, &PointList[i].y); if (i < 10) max1 = max1 | (1 << i); else max2 = max2 | (1 << (i - 10)); } i = n; while (i--) { int j = 0; while (j < i) { g_nPointList[i][j] = abs(PointList[i].x, PointList[j].x) + abs(PointList[i].y, PointList[j].y); j++; } } i = n; initailArray(max1 + 1, max2 + 1); valuex = max1, valuey = max2; printf("%d\n", DeepInto(i)); } } return 0; }
20 个点的数据的时候 要大概3S左右：
例如这组
20
1 2
1000 1
1000 2
3 5
8 11111
222 156
123 123
125 159
11111 12
2101 23
15687 1264
456 4561
121 2315
1 123
1 3
2 56
6 98
9000 12
6000 112
2 1111
求高手解答..代码基本无注释，不好意思..
我的思路：穷举搜索的话 次数超多死T，T的原因应该是 很多组数据时重复在做的，所以，我用一个 二维数组保存做过的 组合，减少重复量，不过我能做的也就这么多....还是不行，20个点搜索 还是要 3S 多...
[解决办法]
是一个动态规划算法：
输入点对 P1, P2, P3, ... , Pn
点对的和表示为: distance(i,j)
1，最优子结构显而易见，从最优解中任意剔除一对点，得到的点对也是剩余的点的最优解。
2，递归函数：
递归函数S（len, i, j)定义为：从输入中获取len对点对 ，且所有点对中不包含点Pi，Pj时，可以找到的所有的len对点对中的最小长度和。 1 <= len <= n / 2, 1 <= i, j <= n;
E(len，i,j,k），表示某个最优解为S(len, i, j)的子问题中是否含有Pk，用0代表S(len, i, j)包含Pk，
S(len, i, j, k) = min { S(len - 1, i, j) + distance(k, l) : E(len - 1, i, j, k）和E(len - 1, i, j, l)等于1（即点Pk,Pl,不在S(len - 1, i, j)的最优解中 }
因为最优子结构特性，E(len - 1, i, j, k)的取值除增加一个新的点对外，其余取值与E（len, i, j, k)相同，那么自底向上的计算S(len, i, j)时，可以把一系列的E（len, i, j, k)，合并成一个E(i, j,k)，当递归计算在len时，E(i,j,k)即代表E(len - 1, i, j, k)。
贴下代码：
- C/C++ code
#include <iostream>using namespace std;class Point { friend class MinPairs; int x, y;public: Point(int x_ = 0, int y_ = 0) : x(x_), y(y_) { }; Point(const Point &p) { x = p.x; y = p.y; }; const Point &operator= (const Point &p) { if (this == &p) return *this; x = p.x; y = p.y; return *this; } int get_x () { return x; } int get_y () { return y; }};class MinPairs { Point *points; const int length;public: MinPairs(const Point points_[], int len) : length(len) { points = new Point[length]; cout << "points are: " << endl; for (int i = 0; i != length; i++) { points[i] = points_[i]; cout << i << ", (" << points[i].x << ", "; cout << points[i].y << ")" << endl; } } int minimul_sum_of_pairs();private: int distance(const Point &p1, const Point &p2) { return abs(p1.x - p2.x) + abs(p1.y - p2.y); } int abs(int n) { return n < 0 ? -n : n; }};int MinPairs::minimul_sum_of_pairs(){ int S[length / 2 + 1][length][length]; unsigned char E[length][length][length]; int min, min_i, min_j; for (int i = 0; i != length; i++) for (int j = 0; j != length; j++) S[0][i][j] = 0; for (int i = 0; i != length; i++) for (int j = 0; j != length; j++) for (int k = 0; k != length; k++) E[i][j][k] = 1; for (int pair_len = 1; pair_len != length / 2; pair_len++) { for (int i = 0; i != length; i++) { for (int j = i + 1; j != length; j++) { min = 2147483647; for (int k = 0; k != length; k++) { for (int l = k + 1; l != length; l++) { if (k == i || k == j || l == i || l == j) continue; if (E[i][j][k] == 0 || E[i][j][l] == 0) continue; int m = S[pair_len - 1][i][j] + distance(points[k], points[l]); if (min > m) { min = m; min_i = k; min_j = l; } } } E[i][j][min_i] = E[i][j][min_j] = 0; S[pair_len][i][j] = S[pair_len][j][i] = min; cout << "pair_len " << pair_len << " without "; cout << "(" << i << "(" << points[i].x << "," << points[i].y <<"),"; cout << j << "(" << points[j].x << "," << points[j].y << ")"; cout << "has minimul sum : " << min << endl; } } } /* 到这里，得到了所有只差一个点对的系列子问题， S( length / 2 - 1, i, j)，对所有点对（i, j)判断，就可得到最优解 */ min = 2147483647; for (int i = 0; i != length; i++) { for (int j = i + 1; j != length; j++) { if (i == j) continue; if (min > S[length / 2 - 1][i][j] + distance(points[i], points[j])) { min = S[length / 2 - 1][i][j] + distance(points[i], points[j]); min_i = i; min_j = j; } } } return min;}int main(){ Point points[] = {Point(1,9), Point(3,5), Point(5,30), Point(0, 0), Point(23,8), Point(24,12), Point(17,34),Point(15,50), Point(45,278),Point(35,89), Point(170,243),Point(48,72), Point(62,39), Point(2,4), Point(5,7), Point(82,26), Point(22,93), Point(70,1), Point(40,9), Point(40,35) }; MinPairs mp(points, sizeof(points) / sizeof(Point)); cout << "minumul : " << mp.minimul_sum_of_pairs() << endl;}
[解决办法]
除了57、58楼的办法（主要是匈牙利法）外……
还尝试了C(19,9)*P(10,10)的枚举（计算了很长的时间才算完）……
算出的结果也是19383……
【程序（纯枚举/验证用）】
- C/C++ code
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <windows.h>struct node{ int x,y;}list[20];int map[20][20];int X[10];int Y[10];int t;int p[10];int c[10];int tmp[10];int savex[10];int savey[10];int ruler[20];int km(){ int i,j,k,flg; int a,b; memset(p,0,sizeof(int)*t); memset(c,0,sizeof(int)*t); memcpy(savex,X,sizeof(int)*t); k=0;flg=1; a=-1; while(flg){ for(p[k]=0;p[k]<t;p[k]++){ for(i=0;i<k;i++){ if(p[i]==p[k]) break; } if(i!=k) continue; c[k]++; if(k==t-1){ /////////////////////////////////////// b=0; for(i=0;i<t;i++) b+=map[X[i]][Y[p[i]]]; if(a==-1||b<a){ a=b; for(i=0;i<t;i++) savey[i]=Y[p[i]]; } /////////////////////////////////////// for(i=t-1,j=1;c[i]==j&&i>=0;i--,j++); if(j==t+1){ flg=0;break; } k=i; if(k<t-1){ memset(c+k+1,0,sizeof(int)*(t-k-1)); } } else k++; } } return a;}void fun(int n){ int i,j,k,a,b; int sum; int tm; int x,flg; if(n==2){ printf("%d\n",abs(list[0].x-list[1].x)+abs(list[0].y-list[1].y)); return; } memset(map,0,sizeof(int)*20*20); for(i=0;i<n;i++){ for(j=i+1;j<n;j++){ a=abs(list[i].x-list[j].x)+abs(list[i].y-list[j].y); map[i][j]=a; map[j][i]=a; } } if(n==4){ a=map[0][1]+map[2][3]; b=map[0][2]+map[1][3]; if(b<a) a=b; b=map[0][3]+map[2][4]; if(b<a) a=b; printf("%d\n",a); return; } t=n/2; sum=0; //for(i=0;i<n;i=i+2) sum+=map[i][i+1]; for(i=0;i<t;i++) X[i]=i; tm=0; sum=19383;//sl point1 while(1){ GetTickCount(); i=0;j=1;k=1; flg=1; while(i<t){ if(k==X[j]&&j<t){ k++;j++; }else{ Y[i]=k;i++;k++; } } tm++; if(tm>=76470){//sl point2 if(tm==80000) break;//sl point3 if(tm%10==0){ printf("."); if(tm%100==0) printf("\ntm: [%d]\n",tm); fflush(stdout); } a=km(); if(a<sum){ printf("\n"); for(x=0;x<t;x++){ printf("%5d\t(%5d,%5d)(%5d,%5d)\n",map[savex[x]][savey[x]],list[savex[x]].x,list[savex[x]].y,list[savey[x]].x,list[savey[x]].y); } sum=a;printf("[%d] sum=%d\n",tm,sum); fflush(stdout); } } if(X[t-1]==n-1){ for(i=t-2,j=n-2;i>=1;i--,j--) if(X[i]!=j) break; if(i==0) break; for(j=X[i]+1;i<t;i++,j++) X[i]=j; }else X[t-1]++; } printf("\nsum: %d\n",sum);}int main(){ int i,c,n; int x,y; scanf("%d",&c); while(c--){ scanf("%d",&n); for(i=0;i<n;i++){ scanf("%d %d",&x,&y); list[i].x=x; list[i].y=y; } fun(n); } return 0;}
[解决办法]
还是没想全面，原来的实现由所有子问题在O(n^2)内解出新问题，原来不全面的思路基于子问题和新问题是否“交叉”，分别求出两种情况下的最小值，但这不全面。
求一新问题S(len,i,j)的最小值时，假定新问题包括某一点对(k,l)，考虑下面两种情况：
1，如果S(len-1,k,l)不包括i和j，那么如果包含(k,l)的S(len,i,j)最小值肯定是等于S(len-1,k,l)+d(k,l)，因为S(len-1,k,l)的意思就是长度为len-1且不包括(k,l)的子问题最优解。如此，列出所有(k,l)的情况。
2，如果S(len-1,k,l)包含了i,j，这时不应该舍弃(k,l)，而是应该在长度为len-1的所有(n^2/2-n)个子问题S(len-1,x,y)中选择一个不包含(k,l)和(i,j)的子问题S(len-1,sub_i,sub_j)，由S(len-1,sub_i,sub_j)+d(k,l)构成使。
S(len,i,j)最终取值为：所有(k,l)点对假设中得到的一系列S(len,i,j)的最小值，
从for循环上看，时间复杂度是：O(n^7)，
直觉上，S数组代表共有n^3/2个子问题，每个子问题由(n^2/2-n)个(k,l)假设计算得到，每个(k,l)假设)要考虑所有len-1的(n^2/2 - n)个子问题，所以t = O(n^7)，
这就相当慢了，也只能算算20个点。
希望现在的代码没有问题！！！！！！
- C/C++ code
int MinPairs::minimum_sum_of_pairs(){ int px[length / 2 + 1][length][length]; int py[length / 2 + 1][length][length]; int S[length / 2 + 1][length][length]; unsigned char E[length/2+1][length][length][length]; int m, min, sub_i, sub_j, new_i, new_j; for (int i = 0; i != length; i++) for (int j = 0; j != length; j++) S[0][i][j] = 0; for (int i = 0; i != length; i++) for (int j = 0; j != length; j++) for (int k = 0; k != length; k++) E[0][i][j][k] = 1; for (int pair_len = 1; pair_len != length / 2; pair_len++) { for (int i = 0; i != length; i++) { for (int j = i + 1; j != length; j++) { min = 2147483647; int sub_i, sub_j, new_i, new_j; for (int k = 0; k != length; k++) { if (k == i || k == j) continue; for (int l = k + 1; l != length; l++) { if (l == i || l == j) continue; if (E[pair_len - 1][k][l][i] == 0 || E[pair_len - 1][k][l][j] == 0) { for (int si = 0; si != length; si++) for (int sj = si + 1; sj != length; sj++) if (E[pair_len - 1][si][sj][i] == 1 && E[pair_len - 1][si][sj][j] == 1 && E[pair_len - 1][si][sj][k] == 1 && E[pair_len - 1][si][sj][l] == 1) { if (min > S[pair_len - 1][si][sj] + d(k, l)) { min = S[pair_len - 1][si][sj] + d(k, l); sub_i = si; sub_j = sj; new_i = k; new_j = l; } } } else { if (min > S[pair_len - 1][k][l] + d(k, l)) { min = S[pair_len - 1][k][l] + d(k, l); sub_i = k; sub_j = l; new_i = k; new_j = l; } } } } S[pair_len][i][j] = min; px[pair_len][i][j] = new_i; py[pair_len][i][j] = new_j; for (int l = pair_len - 1; l != 0; l--) { px[l][i][j] = px[l][sub_i][sub_j]; py[l][i][j] = py[l][sub_i][sub_j]; } for (int k = 0; k != length; k++) E[pair_len][i][j][k] = E[pair_len - 1][sub_i][sub_j][k]; E[pair_len][i][j][new_i] = E[pair_len][i][j][new_j] = 0; //cout << "pair_len " << pair_len << " without "; //cout << points[i] << "," << points[j]; //cout << " has minimum sum : " << min << endl; } } } // 到这里，得到了所有只差一个点对的系列子问题， S( length / 2 - 1, i, j)， // 对所有点对（i, j)判断，就可得到最优解 min = 2147483647; for (int i = 0; i != length; i++) { for (int j = i + 1; j != length; j++) { if (min > S[length / 2 - 1][i][j] + distance(points[i], points[j])) { min = S[length / 2 - 1][i][j] + distance(points[i], points[j]); sub_i = i; sub_j = j; } } } // 从 px, py中输出最优点对 cout << "pairs:" << endl; cout << points[sub_i] << ", \t" << points[sub_j] << endl; for (int len = length / 2 - 1; len != 0; len--) { new_i = px[len][sub_i][sub_j]; new_j = py[len][sub_i][sub_j]; cout << points[new_i] << ", \t" << points[new_j] << endl; } return min;}
[解决办法]
LZ试试这样的数据结构，先对所有的点按照x坐标排个序，逐一加入树结构，
用第一个点作为根节点，第2个点作为叶子节点，加入第3个节点P3，
如果p3到p1的距离D[1,3] < D[2,3]，再比较D[1,2]和D[2,3]，如果D[1,2] < D[2,3]
则说明p1在p2，p3之间，则将节点顺序调整为p3,p1,p2
如果D[1,2] < D[2,3]则说明p3在p1，p2之间，则将节点顺序调整为p1,p3,p2
如果p3到p1的距离D[1,3] > D[2,3]，进行同样类似的比较，调整节点顺序。
每次加入一个新的节点，就不断按照上面的方法调整节点顺序，直到最后一个节点加入
这样一个完整的链表就形成了。按照顺序取点应该就可以了！