题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=20846
POJ 3026是同样的题，但是内存要求比较严格，并是没有过。。。
对以迷宫形式给定的一些点求最小生成树，不过这里的边并不是抽象的两点间笛卡尔距离，也不是折线距离（迷宫中有障碍），而是需要用四个方向的搜索来求。
用bfs求出任两点间的最短距离后，可用kruscal求出最小生成树。
这次值得一提的是对并查集的一点改造：由于每个顶点由一组(x,y)坐标唯一确定，而并查集的元素应是能用一个整数唯一确定的，所以要将(x,y)坐标的集合映射到整数集合。联想到了最近课内学的信道的“分频复用”，和实时操作系统uCOS-II的任务就绪表的数据结构和算法。于是就有了如下做法，其实很常见了~
x,y坐标范围是[0,50]，50<2^6，因此可用一个int型（2^31）的低7位存y坐标，8~14位存x坐标，14<31，一个整型完全可以存下。这样一个点可由一个int型数(低14位)完全确定，并且以每维2^14为size开二维数组vis和dis也可以开下。
经检验这个做法可行，其实就是模仿底层，把基本型当作结构体看待，每位的语义是约定好的，自己编码自己解码~
代码在UVA过了（没限制内存），在POJ上还是MLE，待我好好补一补搜索再来更新吧~
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #include <stack> 6 #include <vector> 7 #include <queue> 8 using namespace std; 9 const int MAX_S=55; 10 const int MAX_N=105; 11 struct Point 12 { 13 int x,y; 14 Point(){} 15 Point(int xx,int yy):x(xx),y(yy){} 16 }; 17 18 struct Edge 19 { 20 Point u,v; 21 int w; 22 }e[MAX_N*MAX_N]; 23 bool cmp(const Edge e1,const Edge e2) 24 { 25 return e1.w<e2.w; 26 } 27 28 int par[(MAX_S<<7)+MAX_S]; 29 void init() 30 { 31 memset(par,-1,sizeof(par)); 32 } 33 int find(int x) 34 { 35 if(par[x]==-1) return x; 36 return par[x]=find(par[x]); 37 } 38 void unite(Point p1,Point p2) 39 { 40 int x=(p1.x<<7)+p1.y; 41 int y=(p2.x<<7)+p2.y; 42 x=find(x); 43 y=find(y); 44 if(x==y) return ; 45 par[x]=y; 46 } 47 48 bool same(Point p1,Point p2) 49 { 50 int x=(p1.x<<7)+p1.y; 51 int y=(p2.x<<7)+p2.y; 52 return find(x)==find(y); 53 } 54 55 int T; 56 int w,h; 57 int n,m; 58 char maze[MAX_S][MAX_S]; 59 int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; 60 61 typedef pair<Point,int> P; 62 int vis[MAX_S][MAX_S]; 63 int dis[(MAX_S<<7)+MAX_S][(MAX_S<<7)+MAX_S]; 64 65 void bfs(int x,int y) 66 { 67 int poi=(x<<7)+y; 68 memset(vis,0,sizeof(vis)); 69 queue<P> que;//Point,step 70 que.push(P(Point(x,y),0)); 71 vis[x][y]=1; 72 while(!que.empty()) 73 { 74 Point p=que.front().first; 75 int step=que.front().second; 76 que.pop(); 77 for(int i=0;i<4;i++) 78 { 79 int nx=p.x+dx[i]; 80 int ny=p.y+dy[i]; 81 int npoi=(nx<<7)+ny; 82 if(nx<0||ny<0||w<=nx||w<=ny||vis[nx][ny]) continue; 83 if(maze[nx][ny]=='#'){vis[nx][ny]=1; continue;} 84 if(dis[poi][npoi]||poi==npoi) continue; 85 que.push(P(Point(nx,ny),step+1)); 86 vis[nx][ny]=1; 87 if((maze[nx][ny]=='A'||maze[nx][ny]=='S')&&poi!=npoi) 88 { 89 e[m].u=Point(x,y); 90 e[m].v=Point(nx,ny); 91 dis[npoi][poi]=dis[poi][npoi]=e[m].w=step+1; 92 m++; 93 } 94 } 95 } 96 } 97 98 int kruscal() 99 { 100 init(); 101 int ans=0; 102 for(int i=0;i<m;i++) 103 { 104 if(!same(e[i].u,e[i].v)) 105 { 106 unite(e[i].u,e[i].v); 107 ans+=e[i].w; 108 } 109 } 110 return ans; 111 } 112 113 int main() 114 { 115 freopen("3026.txt","r",stdin); 116 scanf("%d",&T); 117 while(T--) 118 { 119 scanf("%d%d",&w,&h); 120 n=0; 121 getchar(); 122 for(int i=0;i<h;i++) 123 { 124 fgets(maze[i],w,stdin); 125 gets(maze[i+1]); 126 } 127 m=0; 128 memset(dis,0,sizeof(dis)); 129 for(int i=0;i<h;i++) 130 { 131 for(int j=0;j<w;j++) 132 if(maze[i][j]=='A'||maze[i][j]=='S') bfs(i,j); 133 } 134 /* 135 for(int i=0;i<m;i++) 136 printf("%d %d -> %d %d = %d\n",e[i].u.x,e[i].u.y,e[i].v.x,e[i].v.y,e[i].w); 137 */ 138 sort(e,e+m,cmp); 139 printf("%d\n",kruscal()); 140 } 141 return 0; 142 }
