传送门：Navigation Nightmare
参考：1:https://www.cnblogs.com/huangfeihome/archive/2012/09/07/2675123.html
参考：2:http://blog.csdn.net/tc_to_top/article/details/43447727
题意：先给出一个四方形的城市地图的全部信息，
然后在只知道前k条信息的情况下，询问a，b之间的距离，若没连通，输出-1；
思路：
首先，每次询问的K是按升序排列的（讨论版里神牛说的，还有就是题号很有深意）；
这道题让我对并查集有一个新的认识：根的代表性是非常强的！并查集里如果某个节点的改动会影响到整个并查集的所有节点，那么，在union_set的时候只需要改动根节点就可以了，当然，在find_set函数里要对所有节点进行更新（这相当于一种延时标记）。我们知道，find_set函数走了两条路，一条是前往根的路，一条是从跟返回的路，那么，如果发现根已经被改动，必须在从根返回的路上更新经过的所有节点。这在find_set函数里是可以实现的。
//样例7 61 6 13 E6 3 9 E3 5 7 S4 1 3 N2 4 20 W4 7 2 S31 6 11 4 32 6 6
模拟一遍样例，这里是执行完Find(1-7)以后的坐标
t = 1: x[1] = 0， y[1] = 0
x[6] = 13， y[6] = 0
t = 2: x[1] = 0， y[1] = 0
x[6] = 13， y[6] = 0
x[3] = 22， y[3] = 0
t = 3: x[1] = 0， y[1] = 0
x[6] = 13， y[6] = 0
x[3] = 22， y[3] = 0
x[5] = 22， y[5] = -7
t = 4(换原点)：
x[4] = 0， y[4] = 0
x[1] = 0， y[1] = 3
x[6] = 13， y[6] = 3
x[3] = 22， y[3] = 3
x[5] = 22， y[5] = -4
t = 5(换原点)：
x[2] = 0， y[2] = 0
x[4] = -20，y[4] = 0
x[1] = -20，y[1] = 3
x[6] = -7， y[6] = 3
x[3] = 2， y[3] = 3
x[5] = 2， y[5] = -4
t = 6: x[2] = 0， y[2] = 0
x[4] = -20，y[4] = 0
x[1] = -20，y[1] = 3
x[6] = -7， y[6] = 3
x[3] = 2， y[3] = 3
x[5] = 2， y[5] = -4
x[7] = -20，y[7] = -2
/* ???带权并查集；*/#include <cstdio>#include <algorithm>#include <iostream>#include <cstring>using namespace std;const int maxn = 40009;int n,m,fa[maxn],s[maxn],h[maxn];struct node{ ???int a,b,len; ???char c[5];}mp[maxn];void init(){ ???for(int i=1;i<=n;i++) ???????fa[i]=i; ???memset(s,0,sizeof(s)); ???memset(h,0,sizeof(h));}int ab(int x,int y){ ???if(x-y>0)return x-y; ???else return y-x;}int find(int x){ ???if(fa[x]==x)return x; ???int tmp = fa[x]; ???fa[x]=find(fa[x]); ???h[x] = h[x] + h[tmp]; ???// 从根回来的路上更新子节点 ???s[x] = s[x] + s[tmp]; ???return fa[x];}void uni(node t,int dx,int dy){ ???int px = find(t.a); ???int py = find(t.b); ???if(px==py)return; ???fa[px]=py; ???????????????// 随意合并 ???h[px] = h[t.b] - h[t.a] + dx;// 暂且只对根进行偏移 ???s[px] = s[t.b] - s[t.a] + dy; }int main(){ ???scanf("%d%d",&n,&m); ???init(); ???for(int i=0;i<m;i++) ???{ ???????scanf("%d%d%d%s",&mp[i].a, &mp[i].b, &mp[i].len, mp[i].c); ???} ???int q,k=0; ???scanf("%d",&q); ???while(q--) ???{ ???????int l,r,e; ???????scanf("%d%d%d",&l,&r,&e); ????????for(int i=k;i<e;i++) ????????{ ????????????int dx=0,dy=0; ????????????switch(mp[i].c[0]) ????????????{ ????????????????case ‘N‘:dy+=mp[i].len;break; ????????????????case ‘S‘:dy-=mp[i].len;break; ????????????????case ‘E‘:dx+=mp[i].len;break; ????????????????case ‘W‘:dx-=mp[i].len;break; ????????????} ????????????uni(mp[i],dx,dy); ????????} ????????k=e; ????????int pl=find(l),pr=find(r); ????????if(pl!=pr) ????????{ ????????????puts("-1"); ????????} ????????else ?????????{ ????????????printf("%d\n",ab(h[l],h[r])+ab(s[l],s[r])); ????????} ???} ???return 0;}POJ-1984-Navigation Nightmare+带权并查集（中级
原文地址：https://www.cnblogs.com/ckxkexing/p/8510919.html