POJ 1984 Navigation Nightmare(valset)

Description

有n个网格状的农田，每个农田之间有距离，会依次给出关系，在给出关系后询问两个农田之间的曼哈顿距离是多少？

写在前面

在两种情况下我会去看别人写的题解：
1.百wa不得其解
2.代码实现卡在某个点上
解决了这道题目后，自己写题解时要注意写明什么原因看了别人的题解
对于1，写清楚到底wa在哪个点上
对于2，写清楚别人怎么过的那个点

Analyze

对于此题，我对于”方向“无从下手，固然要记录当前结点到祖先节点的方向，开一个char数组标记吗？可路径压缩时又该如何更新彼此的数据？

解决办法：数字化

想想倘若是一维的，可以通过权值的正负区分左右，二维亦是如此。

以N、E为正，S、W为负

把祖先节点放在圆点上，更新每个点相对于祖先节点的NSEW。

那么同一祖先节点的节点间的哈密顿距离也就易求了。

Code

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 40005;

int n, m, k;
char dir[10];
int u[N], v[N], w, ns[N], ew[N], val_ns[N], val_ew[N], pre[N];

int found(int x)
{
    if(pre[x] == -1)
        return x;

    int tem = found(pre[x]);
    ns[x] += ns[ pre[x] ];
    ew[x] += ew[ pre[x] ];
    return pre[x] = tem;
}

void unite(int a, int b, int v_ns, int v_ew)
{
    int aa = found(a);
    int bb = found(b);
    if(aa != bb)
    {
        pre[aa] = bb;
        ns[aa] = -ns[a] + v_ns + ns[b];
        ew[aa] = -ew[a] + v_ew + ew[b];
    }
}

int main()
{
    while(~scanf("%d %d", &n, &m))
    {
        memset(pre, -1, sizeof(pre));
        memset(ns ,  0,  sizeof(ns));
        memset(ew ,  0,  sizeof(ew));
        for(int i = 1; i <= m; ++i)
        {
            scanf("%d%d%d%s", &u[i], &v[i], &w, dir);
            if(dir[0] == 'N')
                val_ns[i] = w;
            else if(dir[0] == 'S')
                val_ns[i] = -w;
            else if(dir[0] == 'E')
                val_ew[i] = w;
            else
                val_ew[i] = -w;
        }

        scanf("%d", &k);
        int cnt = 0;
        for(int i = 0; i < k; ++i)
        {
            int a, b, idx;
            scanf("%d %d %d", &a, &b, &idx);
            while(cnt < idx)
            {
                cnt++;
                unite(u[cnt], v[cnt], val_ns[cnt], val_ew[cnt]);
            }
            if(found(a) != found(b))
                cout << "-1" << '\n';
            else
                cout << abs(ns[a] - ns[b]) + abs(ew[a] - ew[b]) << '\n';
        }
    }
    return 0;
}