一、题面
POJ1984
二、分析
这题还是比较有意思的一题。
首先需要清楚的是，这题与普通并查集的区别在于它的节点之间的权值是二维的，因为是曼哈顿距离，肯定不能直接存距离，这样将不利于后面的路径压缩更新。
再看如何解题，先要把输入的数据存起来，因为后面是询问，关于方向的处理直接用正负即可。
存好数据后，每次进行询问时，对询问时间点前的进行合并，在并查集的路径压缩里注意这里还是使用了矢量的思想，具体的可以画两个矢量就出来了。
当查询的父节点相同时，表示是连通的，直接算曼哈顿距离就可以了。
当查询的父节点不相同时，表示不是连通的，输出-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\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 }POJ_1984 Navigation Nightmare 【并查集】
原文地址：https://www.cnblogs.com/dybala21/p/10147970.html