一、题面
二、分析
这题还是比较有意思的一题。
首先需要清楚的是，这题与普通并查集的区别在于它的节点之间的权值是二维的，因为是曼哈顿距离，肯定不能直接存距离，这样将不利于后面的路径压缩更新。
再看如何解题，先要把输入的数据存起来，因为后面是询问，关于方向的处理直接用正负即可。
存好数据后，每次进行询问时，对询问时间点前的进行合并，在并查集的路径压缩里注意这里还是使用了矢量的思想，具体的可以画两个矢量就出来了。
当查询的父节点相同时，表示是连通的，直接算曼哈顿距离就可以了。
当查询的父节点不相同时，表示不是连通的，输出-1。
三、AC代码
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 7 using namespace std; 8 9 const int MAXN = 4e4+4; 10 //X Y 表示当前节点到父节点的X， Y相对距离 11 //DX DY 表示 输入的两个节点 X， Y相对距离 12 int X[MAXN], Y[MAXN], DX[MAXN], DY[MAXN]; 13 int First[MAXN], Second[MAXN]; 14 int Par[MAXN]; 15 16 void Init() 17 { 18 memset(X, 0, sizeof(X)); 19 memset(Y, 0, sizeof(Y)); 20 memset(Par, -1, sizeof(Par)); 21 } 22 23 int Find(int a) 24 { 25 if(Par[a] == -1) return a; 26 int t = Par[a]; 27 Par[a] = Find(Par[a]); 28 X[a] += X[t]; 29 Y[a] += Y[t]; 30 return Par[a]; 31 } 32 33 void Union(int a, int b, int dx, int dy) 34 { 35 int fa = Find(a); 36 int fb = Find(b); 37 if(fa != fb) 38 { 39 Par[fa] = fb; 40 X[fa] = X[b] + dx - X[a]; 41 Y[fa] = Y[b] + dy - Y[a]; 42 } 43 } 44 45 int main() 46 { 47 //freopen("input.txt", "r", stdin); 48 int N, M, T; 49 while(scanf("%d %d", &N, &M)!=EOF) 50 { 51 Init(); 52 int len; 53 char c; 54 for(int i = 0; i < M; i++) 55 { 56 scanf("%d %d %d %c", &First[i], &Second[i], &len, &c); 57 switch(c) 58 { 59 case 'E': DX[i] = len, DY[i] = 0; break; 60 case 'W': DX[i] = 0-len, DY[i] = 0; break; 61 case 'N': DX[i] = 0, DY[i] = len; break; 62 case 'S': DX[i] = 0, DY[i] = 0-len; break; 63 } 64 } 65 scanf("%d", &T); 66 int t, k = 0; 67 int u, v; 68 for(int i = 0; i < T; i++) 69 { 70 scanf("%d %d %d", &u, &v, &t); 71 for(k; k < t; k++) 72 { 73 Union(First[k], Second[k], DX[k], DY[k]); 74 } 75 int fu = Find(u); 76 int fv = Find(v); 77 if(fu == fv) 78 { 79 printf("%d ", abs(X[u] - X[v]) + abs(Y[u] - Y[v])); 80 } 81 else 82 { 83 printf("-1 "); 84 } 85 86 } 87 88 } 89 return 0; 90 }