poj1984（带权并查集）

题目链接：http://poj.org/problem?id=1984

题意：给定n个farm，m条边连接farm，k组询问，询问根据前t3条边求t1到t2的曼哈顿距离，若不可求则输出-1。

思路：类似与poj1182，也是并查集的向量运用。用root[i]表示farm i的祖先，x[i],y[i]分别表示i到其祖先的曼哈顿距离的横纵坐标，这里离线化先保存边的信息，在询问的时候更新边的信息，具体的合并操作时x[i],y[i]的运算手动推一下就明白了。

AC代码：

 #include<cstdio>

 #include<cstdlib>

 using namespace std;

 const int maxn=;

 struct node{

     int f1,f2,l;

     char c;

 }a[maxn];

 int n,m,k,root[maxn],x[maxn],y[maxn];

 int getr(int kk){

     if(root[kk]==kk) return kk;

     else{

         int tmp=root[kk];

         root[kk]=getr(root[kk]);

         x[kk]+=x[tmp];

         y[kk]+=y[tmp];

         return root[kk];

     }

 }

 int main(){

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

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

         root[i]=i,x[i]=y[i]=;

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

         scanf("%d%d%d %c",&a[i].f1,&a[i].f2,&a[i].l,&a[i].c);

     int p=;

     scanf("%d",&k);

     while(k--){

         int t1,t2,t3;

         scanf("%d%d%d",&t1,&t2,&t3);

         for(int i=p+;i<=t3;++i){

             int r1=getr(a[i].f1),r2=getr(a[i].f2),xx,yy;

             if(a[i].c=='N') xx=,yy=a[i].l;

             else if(a[i].c=='S') xx=,yy=-a[i].l;

             else if(a[i].c=='E') xx=a[i].l,yy=;

             else xx=-a[i].l,yy=;

             root[r2]=r1;

             x[r2]=x[a[i].f1]-xx-x[a[i].f2];

             y[r2]=y[a[i].f1]-yy-y[a[i].f2];

         }

         p=t3;

         int r1=getr(t1),r2=getr(t2);

         if(r1==r2)

             printf("%d\n",abs(x[t1]-x[t2])+abs(y[t1]-y[t2]));

         else

             printf("-1\n");

     }

     return ;

 }