这道题和poj的食物链很像，要在路径压缩的过程中进行坐标的位置处理，要保存的是当前节点相对于父节点的相对坐标位置。合并的时候要考虑清楚两个父节点之间的坐标关系是什么
View Code
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define N 40005 5 using namespace std; 6 struct node 7 { 8 int p; 9 int x,y; 10 int r; 11 int xd,yd; 12 }; 13 int n; 14 node f[N]; 15 void init() 16 { 17 int i; 18 for(i=1;i<=n;i++) 19 { 20 f[i].p=i; 21 f[i].x=f[i].y=f[i].r=f[i].xd=f[i].yd=0; 22 } 23 } 24 int find(int i) 25 { 26 if(i==f[i].p) 27 return i; 28 int temp=f[i].p; 29 f[i].p=find(temp); 30 f[i].x=f[temp].x+f[i].xd;//路径压缩时进行坐标位置处理，xd,yd为相对父节点的坐标位置 31 f[i].y=f[temp].y+f[i].yd; 32 f[i].xd=f[i].x; 33 f[i].yd=f[i].y; 34 return f[i].p; 35 } 36 void uni(int i,int j,int dir,int len) 37 { 38 int t1=find(i); 39 int t2=find(j); 40 //printf("%d %d\n",dir,len); 41 f[t2].p=t1; 42 if(dir==1)//合并时两个父节点的相对位置 43 { 44 f[t2].xd=f[i].x-f[j].x; 45 f[t2].yd=f[i].y+len-f[j].y; 46 } 47 else if(dir==2) 48 { 49 f[t2].xd=f[i].x-f[j].x; 50 f[t2].yd=f[i].y-len-f[j].y; 51 } 52 else if(dir==3) 53 { 54 f[t2].xd=f[i].x+len-f[j].x; 55 f[t2].yd=f[i].y-f[j].y; 56 } 57 else 58 { 59 f[t2].xd=f[i].x-len-f[j].x; 60 f[t2].yd=f[i].y-f[j].y; 61 } 62 } 63 int main() 64 { 65 int s[26]; 66 s['U'-'A']=1; 67 s['D'-'A']=2; 68 s['R'-'A']=3; 69 s['L'-'A']=4; 70 char s2[100]; 71 char s3[10]; 72 int m,i,j,a,b,len; 73 while(scanf("%d%d",&n,&m)!=EOF) 74 { 75 init(); 76 while(m--) 77 { 78 scanf("%s",s2); 79 if(s2[0]=='Q') 80 { 81 scanf("%d %d",&a,&b); 82 if(find(a)==find(b)) 83 printf("%d\n",abs(f[a].x-f[b].x)+abs(f[a].y-f[b].y)); 84 else 85 printf("-1\n"); 86 } 87 else if(s2[0]=='A') 88 { 89 scanf("%d %d %d %s",&a,&b,&len,s3); 90 uni(a,b,s[s3[0]-'A'],len); 91 //printf("%d %s\n",m,s2); 92 } 93 } 94 } 95 return 0; 96 }