BZOJ_3362_[Usaco2004 Feb]Navigation Nightmare 导航噩梦_并查集
Description
农夫约翰有N(2≤N≤40000)个农场，标号1到N,M(2≤M≤40000)条的不同的垂直或水
平的道路连结着农场，道路的长度不超过1000.这些农场的分布就像下面的地图一样，
图中农场用F1..F7表示, 每个农场最多能在东西南北四个方向连结4个不同的农场．此外，农场只处在道路的两端．道路不会交叉且每对农场间有且仅有一条路径．邻居鲍伯要约翰来导航，但约翰丢了农场的地图，他只得从电脑的备份中修复了．每一条道路的信息如下：
从农场23往南经距离10到达农场17
从农场1往东经距离7到达农场17
当约翰重新获得这些数据时，他有时被的鲍伯的问题打断：“农场1到农场23的曼哈顿距离是多少？”所谓在(XI，Yi)和(X2，y2)之间的“曼哈顿距离”，就是lxl - X21+lyl - y21．如果已经有足够的信息，约翰就会回答这样的问题（在上例中答案是17），否则他会诚恳地抱歉并回答-1.
Input
第1行：两个分开的整数N和M.
第2到M+1行：每行包括4个分开的内容，F1，F2，三，D分别描述两个农场的编号，道路的长度，F1到F2的方向N，E，S，w．
第M+2行：一个整数，K(1≤K≤10000)，表示问题个数．
第M+3到M+K+2行：每行表示一个问题，由3部分组成：Fi，F2，，．其中Fi和F2表示两个被问及的农场．而/(1≤J≤M)表示问题提出的时刻．J为1时，表示得知信息1但未得知信息2时．
Output
第1到K行：每行一个整数，回答问题．表示两个农场间的曼哈顿距离．不得而知则输出-1.
Sample Input
7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
3
1 6 1
1 4 3
2 6 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
3
1 6 1
1 4 3
2 6 6
Sample Output
13
-1
10
-1
10
将询问排序，每次插边。
用并查集维护出祖先和到祖先的横向距离和纵向距离，find时更新。
代码：
#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;#define N 40050int n,fa[N],xx[N],yy[N],m,ans[N];char opt[10];int Abs(int x) { ???return x>0?x:-x;}struct E { ???int a,b,c,d; ???void rd() { ???????scanf("%d%d%d%s",&a,&b,&c,opt); ???????if(opt[0]==‘N‘) d=1; ???????if(opt[0]==‘S‘) d=2; ???????if(opt[0]==‘W‘) d=3; ???????if(opt[0]==‘E‘) d=4; ???}}e[N];struct Q { ???int t,x,y,id; ???void rd(){scanf("%d%d%d",&x,&y,&t);} ???bool operator < (const Q &u) const { ???????return t<u.t; ???}}q[N];int find(int x) { ???if(fa[x]==x) return x; ???int tmp=fa[x]; ???fa[x]=find(fa[x]); ???xx[x]+=xx[tmp]; ???yy[x]+=yy[tmp]; ???return fa[x];}void add(int x) { ???int a=e[x].a,b=e[x].b,c=e[x].c,d=e[x].d; ???int da=find(a),db=find(b); ???fa[da]=db; ???// if(ta != tb) f[ta] = tb , dx[ta] = dx[b[t]] + cx[t] - dx[a[t]] , dy[ta] = dy[b[t]] + cy[t] - dy[a[t]]; ???if(d==1) { ???????xx[da]=xx[b]-xx[a]; ???????yy[da]=yy[b]-yy[a]-c; ???}else if(d==2) { ???????xx[da]=xx[b]-xx[a]; ???????yy[da]=yy[b]-yy[a]+c; ???}else if(d==3) { ???????xx[da]=xx[b]-xx[a]-c; ???????yy[da]=yy[b]-yy[a]; ???}else { ???????xx[da]=xx[b]-xx[a]+c; ???????yy[da]=yy[b]-yy[a]; ???}}int query(int x,int y) { ???int dx=find(x),dy=find(y); ???if(dx!=dy) return -1; ???return Abs(xx[x]-xx[y])+Abs(yy[x]-yy[y]);}int main() { ???scanf("%d%*d",&n); ???int i; ???for(i=1;i<=n;i++) fa[i]=i; ???for(i=1;i<n;i++) { ???????e[i].rd(); ???} ???scanf("%d",&m); ???for(i=1;i<=m;i++) { ???????q[i].rd(); q[i].id=i; ???} ???sort(q+1,q+m+1); ???int now=1; ???for(i=1;i<=m;i++) { ???????while(now<=q[i].t) { ???????????add(now); now++; ???????} ???????ans[q[i].id]=query(q[i].x,q[i].y); ???} ???for(i=1;i<=m;i++) { ???????printf("%d\n",ans[i]); ???}}BZOJ_3362_[Usaco2004 Feb]Navigation Nightmare 导航噩梦_并查集
原文地址：https://www.cnblogs.com/suika/p/9062502.html