本文主要是介绍POJ 1984 Navigation Nightmare 二维带权并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目来源：POJ 1984 Navigation Nightmare
题意：给你一颗树 k次询问 求2点之间的曼哈顿距离 并且要在只有开始k条边的情况下
思路：按照方向 我是以左上角为根 左上角为原点 dx[i]为i点距离根的x坐标 dy[]是y坐标 这两个可以通过路径压缩求出 只不过是二维而已
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxn = 40010;
int f[maxn], dx[maxn], dy[maxn];struct node
{int u, v, w;char s[3];
}a[maxn];
void init(int n)
{for(int i = 1; i <= n; i++)f[i] = i;memset(dx, 0, sizeof(dx));memset(dy, 0, sizeof(dy));
}int find(int x)
{if(x != f[x]){int rt = find(f[x]);dx[x] += dx[f[x]];dy[x] += dy[f[x]];f[x] = rt;return rt;}return x;
}
int main()
{int n, m;scanf("%d %d", &n, &m);init(n);for(int i = 1; i <= m; i++){scanf("%d %d %d %s", &a[i].u, &a[i].v, &a[i].w, a[i].s);}int q;scanf("%d", &q);int i = 1;while(q--){int s, e, w;scanf("%d %d %d", &s, &e, &w);while(i <= m && i <= w){int u = a[i].u;int v = a[i].v;int x = find(u);int y = find(v);if(x == y)continue;if(a[i].s[0] == 'E'){f[y] = x;dx[y] = dx[u]-dx[v]+a[i].w;dy[y] = dy[u]-dy[v];}else if(a[i].s[0] == 'W'){f[x] = y;dx[x] = dx[v]-dx[u]+a[i].w;dy[x] = dy[v]-dy[u];}else if(a[i].s[0] == 'N'){f[x] = y;dy[x] = dy[v]-dy[u]+a[i].w;dx[x] = dx[v]-dx[u];}else{f[y] = x;dy[y] = dy[u]-dy[v]+a[i].w;dx[y] = dx[u]-dx[v];}i++;} int x = find(s);int y = find(e);if(x == y){int d = abs(dx[s]-dx[e]) + abs(dy[s]-dy[e]);printf("%d\n", d);}else{puts("-1");}}return 0;
}
这篇关于POJ 1984 Navigation Nightmare 二维带权并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
