学步园

http://poj.org/problem?id=1984

    题目描述的如此蛋疼。。。

    关系并查集，用cx和cy数组记录点与根结点的相对位置，然后根据输入依次合并，当碰到询问时便计算距离，若不在同一集合中，即无法确定相对位置。

code:

#include<cstdio>
#include<cstring>
int p[40001], cx[40001], cy[40001] ;
int f1[10001], f2[10001], fi[10001] ;
struct edge{
    int s, e, l ;
    char d ;
}q[40001] ;
int abs(int a){
    return a>0?a:-a ;
}
void make_set(int n){
    for(int i=0; i<=n+1; i++){
        p[i] = i ;
        cx[i] = cy[i] = 0 ;
    }
}
int find_set(int x){
    int temp ;
    if(x!=p[x]){
        temp = p[x] ;
        p[x] = find_set(p[x]) ;
        cx[x] = cx[temp] + cx[x] ;
        cy[x] = cy[temp] + cy[x] ;
    }
    return p[x] ;
}
void union_set(int x){
    int a = q[x].s ;
    int b = q[x].e ;
    int pa = find_set(a) ;
    int pb = find_set(b) ;
    p[pb] = pa ;
    cx[pb] = cx[a] - cx[b] ;
    cy[pb] = cy[a] - cy[b] ;
    switch(q[x].d){
        case 'E':cx[pb] += q[x].l ;break ;
        case 'W':cx[pb] -= q[x].l ;break ;
        case 'N':cy[pb] += q[x].l ;break ;
        case 'S':cy[pb] -= q[x].l ;break ;
    }
    return ;
}
int main(){
    int n, m, k, i, j, t, x, y, z, tx, ty ;
    while(~scanf("%d%d", &n, &m)){
        make_set(n) ;
        for(i=1; i<=m; i++)
            scanf("%d %d %d %c", &q[i].s, &q[i].e, &q[i].l, &q[i].d) ;
        scanf("%d", &t) ;
        for(i=0; i<t; i++)
            scanf("%d%d%d", &f1[i], &f2[i], &fi[i]) ;
        int temp = 0 ;
        for(i=1; i<=m; i++){
            tx = find_set(q[i].s) ;
            ty = find_set(q[i].e) ;
            if(tx!=ty)
                union_set(i) ;
            while(fi[temp]==i){
                tx = find_set(f1[temp]) ;
                ty = find_set(f2[temp]) ;
                if(tx!=ty)  printf("-1\n") ;
                else{
                    tx = abs(cx[f1[temp]] - cx[f2[temp]]) ;
                    ty = abs(cy[f1[temp]] - cy[f2[temp]]) ;
                    printf("%d\n", tx + ty) ;
                }
                temp ++ ;
            }
        }
    }
    return 0 ;}