这题还是比较有意思的一题。
首先需要清楚的是,这题与普通并查集的区别在于它的节点之间的权值是二维的,因为是曼哈顿距离,肯定不能直接存距离,这样将不利于后面的路径压缩更新。
再看如何解题,先要把输入的数据存起来,因为后面是询问,关于方向的处理直接用正负即可。
存好数据后,每次进行询问时,对询问时间点前的进行合并,在并查集的路径压缩里注意这里还是使用了矢量的思想,具体的可以画两个矢量就出来了。
当查询的父节点相同时,表示是连通的,直接算曼哈顿距离就可以了。
当查询的父节点不相同时,表示不是连通的,输出-1。
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\n", abs(X[u] - X[v]) + abs(Y[u] - Y[v]));80 }81 else82 {83 printf("-1\n");84 }85 86 }87 88 }89 return 0;90 }
View Code