poj1984 带权并查集

题意：有多个点，在平面上位于坐标点上，给出一些关系，表示某个点在某个点的正东/西/南/北方向多少距离，然后给出一系列询问，表示在第几个关系给出后询问某两点的曼哈顿距离，或者未知则输出-1。

只要在元素的权值上保存两个信息，与祖先元素的两个方向的差，我选择正东和正北方向差（负值表示正西和正南），然后直接用带权并查集，询问时曼哈顿距离就是两个权值的绝对值之和。由于询问是嵌在给出关系中间的，所以要先存下所有关系和询问，离线做就行。

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 using namespace std;

 const int maxm=4e4+;

 int fa[maxm],north[maxm],east[maxm];

 int a[maxm],b[maxm],l[maxm],ans[];

 char s[maxm][];

 struct que{

     int num,a,b,t;

     bool operator < (const que a)const{

         return t<a.t;

     }

 }q[];

 int abs(int a){return a>?a:-a;}

 void init(int n){

     for(int i=;i<=n;++i){

         fa[i]=i;

         north[i]=east[i]=;

     }

 }

 int find(int x){

     int r=x,t1,t2,t3,cn=,ce=;

     while(r!=fa[r]){

         cn+=north[r];

         ce+=east[r];

         r=fa[r];

     }

     while(x!=r){

         t1=fa[x];

         t2=cn-north[x];

         t3=ce-east[x];

         north[x]=cn;

         east[x]=ce;

         fa[x]=r;

         cn=t2;

         ce=t3;

         x=t1;

     }

     return r;

 }

 int main(){

     int n,m;

     scanf("%d%d",&n,&m);

     init(n);

     for(int i=;i<=m;++i)scanf("%d%d%d%s",&a[i],&b[i],&l[i],s[i]);

     int k;

     scanf("%d",&k);

     for(int i=;i<=k;++i){

         scanf("%d%d%d",&q[i].a,&q[i].b,&q[i].t);

         q[i].num=i;

     }

     sort(q+,q+k+);

     int pos=;

     for(int i=;i<=m;++i){

         int x=find(a[i]),y=find(b[i]);

         int Cn=,Ce=;

         if(s[i][]=='N')Cn=l[i];

         else if(s[i][]=='S')Cn=-l[i];

         else if(s[i][]=='E')Ce=l[i];

         else if(s[i][]=='W')Ce=-l[i];

         if(x!=y){

             fa[x]=y;

             north[x]=north[b[i]]+Cn-north[a[i]];

             east[x]=east[b[i]]+Ce-east[a[i]];

         }

         while(q[pos].t==i&&pos<=k){

             x=find(q[pos].a);

             y=find(q[pos].b);

             if(x!=y)ans[q[pos].num]=-;

             else ans[q[pos].num]=abs(north[q[pos].a]-north[q[pos].b])+abs(east[q[pos].a]-east[q[pos].b]);

             pos++;

         }

     }

     for(int i=;i<=k;++i)printf("%d\n",ans[i]);

     return ;

 }