POJ_1984 Navigation Nightmare 【并查集】

一、题面

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 }

View Code

 

相关文章